Editing Computational complexity theory (section)

===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.