Computability
A problem is computable if an algorithm, given unlimited amounts of time and storage space, will complete in finite time.
Hard Limit of Computability
The hard limit of computability is reached when something is uncomputable, i.e. there can be no algorithm that provides a solution to an uncomputable problem. Undecidable problems reach the hard limit of computability.
Undecidable problems are problems for which it is impossible for there to be an algorithm that always gives a correct solution to a decision problem (a problem that demands a Boolean answer).
Soft Limit of Computability
The soft limit of computability is reached when a problem can be solved, but requires an impractical number of resources (space or time) to be solved. Intractable problems reach the soft limit of computability.
Intractable problems are problems that cannot be solved in polynomial time, and so grow rapidly compared to the input size. This makes them impractical to solve for large inputs.
Tractable problems
A tractable problem is a problem that has a reasonable or polynomial-time complexity. There fore the most efficient algorithm to correctly solve the problem will have the time complexity: