information:extraction, linguistic:voice_change
Intractability

A problem that can theoretically be solved, but requires impractical and finite resources (e.g., time) to do so, is known as an intractable problem. Conversely, a problem that can be solved in practice is called a tractable problem, literally "a problem that can be handled". The term infeasible (literally "cannot be done") is sometimes used interchangeably with intractable, though this risks confusion with a feasible solution in mathematical optimization.

Tractable problems are frequently identified with problems that have polynomial-time solutions (P {\displaystyle P}, P T I M E {\displaystyle PTIME}); this is known as the Cobham–Edmonds thesis. Problems that are known to be intractable in this sense include those that are EXPTIME -hard. If N P {\displaystyle NP} is not the same as P {\displaystyle P}, then NP-hard problems are also intractable in this sense.

However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in P {\displaystyle P} does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in Presburger arithmetic has been shown not to be in P {\displaystyle P}, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete knapsack problem over a wide range of sizes in less than quadratic time and SAT solvers routinely handle large instances of the NP-complete Boolean satisfiability problem.

To see why exponential-time algorithms are generally unusable in practice, consider a program that makes 2 n {\displaystyle 2^{n}} operations before halting. For small n {\displaystyle n}, say 100, and assuming for the sake of example that the computer does 10 12 {\displaystyle 10^{12}} operations each second, the program would run for about 4 × 10 10 {\displaystyle 4\times 10^{10}} years, which is the same order of magnitude as the age of the universe. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes 1.0001 n {\displaystyle 1.0001^{n}} operations is practical until n {\displaystyle n} gets relatively large.

Similarly, a polynomial time algorithm is not always practical. If its running time is, say, n 15 {\displaystyle n^{15}}, it is unreasonable to consider it efficient and it is still useless except on small instances. Indeed, in practice even n 3 {\displaystyle n^{3}} or n 2 {\displaystyle n^{2}} algorithms are often impractical on realistic sizes of problems.