Editing Computational complexity theory (section)

==Intractability== <!-- This section is linked from [[Minimax]], [[Intractability]], [[Intractable]] -->
{{See also|Combinatorial explosion}}
A problem that can theoretically be solved, but requires impractical and infinite resources (e.g., time) to do so, is known as an '''''{{visible anchor|intractable problem}}'''''.<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref> Conversely, a problem that can be solved in practice is called a '''''{{visible anchor|tractable problem}}''''', literally "a problem that can be handled". The term ''[[wikt:infeasible|infeasible]]'' (literally "cannot be done") is sometimes used interchangeably with ''[[wikt:intractable|intractable]]'',<ref>{{cite book |title=Algorithms and Complexity |first=Gerard |last=Meurant |year=2014 |isbn=978-0-08093391-7 |page=[https://books.google.com/books?id=6WriBQAAQBAJ&pg=PA4 p. 4]|publisher=Elsevier }}</ref> though this risks confusion with a [[feasible solution]] in [[mathematical optimization]].<ref>
{{cite book
|title=Writing for Computer Science
|first=Justin
|last=Zobel
|page=[https://books.google.com/books?id=LWCYBgAAQBAJ&pg=PA132 132]
|year=2015
|publisher=Springer
|isbn=978-1-44716639-9
}}</ref>

Tractable problems are frequently identified with problems that have polynomial-time solutions (<math>\textsf{P}</math>, <math>\textsf{PTIME}</math>); 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 <math>\textsf{NP}</math> is not the same as <math>\textsf{P}</math>, 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 <math>\textsf{P}</math> 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 <math>\textsf{P}</math>, 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 solver]]s 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 <math>2^n</math> operations before halting. For small <math>n</math>, say 100, and assuming for the sake of example that the computer does <math>10^{12}</math> operations each second, the program would run for about <math>4 \times 10^{10}</math> 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 <math>1.0001^n</math> operations is practical until <math>n</math> gets relatively large.

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