what is the difference between tractable, intractable and unsolvable algorithms?

Question

farmdawgnation · Answer

So, the tractability of a problem refers to how difficult the problem is in terms of the amount of time it takes for the problem to be solved. This is related to the time complexity of the problem.

A tractable problem can be solved in polynomial time. So, this means that if you have a number of items n, the length of time it will take to solve that problem will be something like $O(n)$ or $O(n^2)$ or so on.

Intractable problems are those that *can* be solved, but the amount of time it takes to solve them is too large. A good example of this type of problem would be trying to brute-force something that's been encrypted using an RSA algorithm. It's possible to do, but by the time you actually find the solution - it will be completely worthless.

Unsolvable problems are just what they sound like - problems that could not be solved given an infinite amount of time.