Editing P versus NP problem (section)

==Does P mean "easy"?==
[[File:KnapsackEmpComplexity.GIF|thumb|310 px|The graph shows the running time vs. problem size for a [[knapsack problem]] of a state-of-the-art, specialized algorithm. The [[Curve fitting|quadratic fit]] suggests that the algorithmic complexity of the problem is O((log(''n''))<sup>2</sup>).<ref name=Pisinger2003>Pisinger, D. 2003. "Where are the hard knapsack problems?" Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark</ref>]]
All of the above discussion has assumed that P means "easy" and "not in P" means "difficult", an assumption known as ''[[Cobham's thesis]]''. It is a common assumption in complexity theory; but there are caveats.

First, it can be false in practice. A theoretical polynomial algorithm may have extremely large constant factors or exponents, rendering it impractical. For example, the problem of [[decision problem|deciding]] whether a graph ''G'' contains ''H'' as a [[graph minor|minor]], where ''H'' is fixed, can be solved in a running time of ''O''(''n''<sup>2</sup>),<ref name="kkr12">{{cite journal |last1=Kawarabayashi | first1=Ken-ichi |last2=Kobayashi | first2=Yusuke |last3=Reed | first3=Bruce | authorlink3=Bruce Reed (mathematician) |year=2012 |title=The disjoint paths problem in quadratic time |journal=[[Journal of Combinatorial Theory]] | series=Series B |volume=102 |issue=2 |pages=424–435|doi=10.1016/j.jctb.2011.07.004 |doi-access=free }}</ref> where ''n'' is the number of vertices in ''G''.  However, the [[big O notation]] hides a constant that depends superexponentially on ''H''.  The constant is greater than <math> 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) </math> (using [[Knuth's up-arrow notation]]), and where ''h'' is the number of vertices in ''H''.<ref>{{cite journal |author=Johnson, David S. |title=The NP-completeness column: An ongoing guide (edition 19) |journal= Journal of Algorithms |volume=8 |issue=2 |year=1987 |pages=285–303 |citeseerx=10.1.1.114.3864 |doi=10.1016/0196-6774(87)90043-5 }}</ref>

On the other hand, even if a problem is shown to be NP-complete, and even if P&nbsp;≠&nbsp;NP, there may still be effective approaches to the problem in practice. There are algorithms for many NP-complete problems, such as the [[knapsack problem]], the [[traveling salesman problem]], and the [[Boolean satisfiability problem]], that can solve to optimality many real-world instances in reasonable time. The empirical [[average-case complexity]] (time vs. problem size) of such algorithms can be surprisingly low.  An example is the [[simplex algorithm]] in [[linear programming]], which works surprisingly well in practice; despite having exponential worst-case [[time complexity]], it runs on par with the best known polynomial-time algorithms.<ref>{{cite book|last1=Gondzio|first1=Jacek|last2=Terlaky|first2=Tamás|chapter=3 A computational view of interior point methods |mr=1438311 |title=Advances in linear and integer programming|pages=103–144|editor=J. E. Beasley|location=New York|publisher=Oxford University Press|year=1996|series=Oxford Lecture Series in Mathematics and its Applications |volume=4 |chapter-url=http://www.maths.ed.ac.uk/~gondzio/CV/oxford.ps|id=[http://www.maths.ed.ac.uk/~gondzio/CV/oxford.ps Postscript file at website of Gondzio] and [http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-94-73.ps.gz at McMaster University website of Terlaky]}}</ref>

Finally, there are types of computations which do not conform to the Turing machine model on which P and NP are defined, such as [[quantum computation]] and [[randomized algorithm]]s.