Editing Computational complexity theory (section)

==Important open problems==
[[Image:Complexity classes.svg|thumb|Diagram of complexity classes provided that P ≠ NP. The existence of problems in NP outside both P and NP-complete in this case was established by Ladner.<ref name="Ladner75">{{Citation|last=Ladner|first=Richard E.|title=On the structure of polynomial time reducibility|journal=[[Journal of the ACM]] |volume=22|year=1975|pages=151–171|doi=10.1145/321864.321877|issue=1|s2cid=14352974|postscript=.|doi-access=free}}</ref>]]

===P versus NP problem===
{{Main|P versus NP problem}}

The complexity class P is often seen as a mathematical abstraction modeling those computational tasks that admit an efficient algorithm. This hypothesis is called the [[Cobham–Edmonds thesis]]. The complexity class [[NP (complexity)|NP]], on the other hand, contains many problems that people would like to solve efficiently, but for which no efficient algorithm is known, such as the [[Boolean satisfiability problem]], the [[Hamiltonian path problem]] and the [[vertex cover problem]]. Since deterministic Turing machines are special non-deterministic Turing machines, it is easily observed that each problem in P is also member of the class NP.

The question of whether P equals NP is one of the most important open questions in theoretical computer science because of the wide implications of a solution.<ref name="Sipser2006">See {{harvnb|Sipser|2006|loc= Chapter 7: Time complexity}}</ref> If the answer is yes, many important problems can be shown to have more efficient solutions. These include various types of [[integer programming]] problems in [[operations research]], many problems in [[logistics]], [[protein structure prediction]] in [[biology]],<ref>{{Citation|title=Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete|last1=Berger|first1=Bonnie A.|author1-link=Bonnie Berger|journal=Journal of Computational Biology|year=1998|volume=5|pages=27–40|pmid=9541869|doi=10.1089/cmb.1998.5.27|last2=Leighton|first2=T|author2-link=F. Thomson Leighton|issue=1|postscript=. |citeseerx=10.1.1.139.5547}}</ref> and the ability to find formal proofs of [[pure mathematics]] theorems.<ref>{{Citation|last=Cook|first=Stephen|author-link=Stephen Cook|title=The P versus NP Problem|publisher=[[Clay Mathematics Institute]]|date=April 2000|url=http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|access-date=2006-10-18|postscript=.|url-status=dead|archive-url=https://web.archive.org/web/20101212035424/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|archive-date=December 12, 2010|df=mdy-all}}</ref> The P versus NP problem is one of the [[Millennium Prize Problems]] proposed by the [[Clay Mathematics Institute]]. There is a US$1,000,000 prize for resolving the problem.<ref>{{Citation|title=The Millennium Grand Challenge in Mathematics|last=Jaffe|first=Arthur M.|author-link=Arthur Jaffe|year=2006|journal=Notices of the AMS|volume=53|issue=6|url=https://www.ams.org/notices/200606/fea-jaffe.pdf |archive-url=https://web.archive.org/web/20060612225513/http://www.ams.org/notices/200606/fea-jaffe.pdf |archive-date=2006-06-12 |url-status=live|access-date=2006-10-18|postscript=.}}</ref>

===Problems in NP not known to be in P or NP-complete===
It was shown by Ladner that if <math>\textsf{P} \neq \textsf{NP}</math> then there exist problems in <math>\textsf{NP}</math> that are neither in <math>\textsf{P}</math> nor <math>\textsf{NP}</math>-complete.<ref name="Ladner75" /> Such problems are called [[NP-intermediate]] problems. The [[graph isomorphism problem]], the [[discrete logarithm problem]] and the [[integer factorization problem]] are examples of problems believed to be NP-intermediate. They are some of the very few NP problems not known to be in <math>\textsf{P}</math> or to be <math>\textsf{NP}</math>-complete.

The [[graph isomorphism problem]] is the computational problem of determining whether two finite [[graph (discrete mathematics)|graph]]s are [[graph isomorphism|isomorphic]]. An important unsolved problem in complexity theory is whether the graph isomorphism problem is in <math>\textsf{P}</math>, <math>\textsf{NP}</math>-complete, or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete.<ref name="AK06">{{Citation
 | first1 = Vikraman
 | last1 = Arvind
 | first2 = Piyush P.
 | last2 = Kurur
 | title = Graph isomorphism is in SPP
 | journal = Information and Computation
 | volume = 204
 | issue = 5
 | year = 2006
 | pages = 835–852
 | doi = 10.1016/j.ic.2006.02.002
 | postscript = .| doi-access = 
 }}</ref> If graph isomorphism is NP-complete, the [[polynomial time hierarchy]] collapses to its second level.<ref>{{citation
 | last = Schöning | first = Uwe | author-link = Uwe Schöning
 | doi = 10.1016/0022-0000(88)90010-4
 | issue = 3
 | journal = Journal of Computer and System Sciences
 | pages = 312–323
 | title = Graph Isomorphism is in the Low Hierarchy
 | volume = 37
 | year = 1988}}</ref> Since it is widely believed that the polynomial hierarchy does not collapse to any finite level, it is believed that graph isomorphism is not NP-complete. The best algorithm for this problem, due to [[László Babai]] and [[Eugene Luks]] has run time <math>O(2^{\sqrt{n \log n}})</math> for graphs with <math>n</math> vertices, although some recent work by Babai offers some potentially new perspectives on this.<ref>{{cite arXiv |last=Babai |first=László |date=2016 |title=Graph Isomorphism in Quasipolynomial Time |eprint=1512.03547 |class=cs.DS }}</ref>

The [[integer factorization problem]] is the computational problem of determining the [[prime factorization]] of a given integer. Phrased as a decision problem, it is the problem of deciding whether the input has a prime factor less than <math>k</math>. No efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic systems, such as the [[RSA (algorithm)|RSA]] algorithm. The integer factorization problem is in <math>\textsf{NP}</math> and in <math>\textsf{co-NP}</math> (and even in UP and co-UP<ref>{{cite web|first=Lance|last=Fortnow|author-link=Lance Fortnow|title=Computational Complexity Blog: Factoring|date=2002-09-13|url=http://weblog.fortnow.com/2002/09/complexity-class-of-week-factoring.html|website=weblog.fortnow.com}}</ref>). If the problem is <math>\textsf{NP}</math>-complete, the polynomial time hierarchy will collapse to its first level (i.e., <math>\textsf{NP}</math> will equal <math>\textsf{co-NP}</math>). The best known algorithm for integer factorization is the [[general number field sieve]], which takes time <math>O(e^{\left(\sqrt[3]{\frac{64}{9}}\right)\sqrt[3]{(\log n)}\sqrt[3]{(\log \log n)^2}})</math><ref>Wolfram MathWorld: [http://mathworld.wolfram.com/NumberFieldSieve.html Number Field Sieve]</ref> to factor an odd integer <math>n</math>. However, the best known [[quantum algorithm]] for this problem, [[Shor's algorithm]], does run in polynomial time. Unfortunately, this fact doesn't say much about where the problem lies with respect to non-quantum complexity classes.

===Separations between other complexity classes===
Many known complexity classes are suspected to be unequal, but this has not been proved. For instance <math>\textsf{P} \subseteq \textsf{NP} \subseteq \textsf{PP} \subseteq \textsf{PSPACE}</math>, but it is possible that <math>\textsf{P} = \textsf{PSPACE}</math>. If <math>\textsf{P}</math> is not equal to <math>\textsf{NP}</math>, then <math>\textsf{P}</math> is not equal to <math>\textsf{PSPACE}</math> either. Since there are many known complexity classes between <math>\textsf{P}</math> and <math>\textsf{PSPACE}</math>, such as <math>\textsf{RP}</math>, <math>\textsf{BPP}</math>, <math>\textsf{PP}</math>, <math>\textsf{BQP}</math>, <math>\textsf{MA}</math>, <math>\textsf{PH}</math>, etc., it is possible that all these complexity classes collapse to one class. Proving that any of these classes are unequal would be a major breakthrough in complexity theory.

Along the same lines, <math>\textsf{co-NP}</math> is the class containing the [[Complement (complexity)|complement]] problems (i.e. problems with the ''yes''/''no'' answers reversed) of <math>\textsf{NP}</math> problems. It is believed<ref>[http://www.cs.princeton.edu/courses/archive/spr06/cos522/ Boaz Barak's course on Computational Complexity] [http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf Lecture 2]</ref> that <math>\textsf{NP}</math> is not equal to <math>\textsf{co-NP}</math>; however, it has not yet been proven. It is clear that if these two complexity classes are not equal then <math>\textsf{P}</math> is not equal to <math>\textsf{NP}</math>, since <math>\textsf{P} = \textsf{co-P}</math>. Thus if <math>P = NP</math> we would have <math>\textsf{co-P} = \textsf{co-NP}</math> whence <math>\textsf{NP} = \textsf{P} = \textsf{co-P} = \textsf{co-NP}</math>.

Similarly, it is not known if <math>\textsf{L}</math> (the set of all problems that can be solved in logarithmic space) is strictly contained in <math>\textsf{P}</math> or equal to <math>\textsf{P}</math>. Again, there are many complexity classes between the two, such as <math>\textsf{NL}</math> and <math>\textsf{NC}</math>, and it is not known if they are distinct or equal classes.

It is suspected that <math>\textsf{P}</math> and <math>\textsf{BPP}</math> are equal. However, it is currently open if <math>\textsf{BPP} = \textsf{NEXP}</math>.