Editing P versus NP problem (section)

==Problems in NP not known to be in P or NP-complete==
{{Main article|NP-intermediate|l1=NP-intermediate}}
In 1975, [[Richard E. Ladner]] showed that if P&nbsp;≠&nbsp;NP, then there exist problems in NP that are neither in P nor NP-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 P or to be NP-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 P, NP-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">{{cite journal
 | 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
 | doi-access = 
 }}</ref> If graph isomorphism is NP-complete, the [[polynomial time hierarchy]] collapses to its second level.<ref>{{cite journal | last1 = Schöning | first1 = Uwe | author-link = Uwe Schöning | year = 1988 | title = Graph isomorphism is in the low hierarchy | journal = Journal of Computer and System Sciences | volume = 37 | issue = 3| pages = 312–323 | doi=10.1016/0022-0000(88)90010-4| doi-access =  }}</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]], runs in [[quasi-polynomial time]].<ref>{{cite conference|last=Babai|first=László|contribution=Group, graphs, algorithms: the graph isomorphism problem|mr=3966534|pages=3319–3336|publisher=World Sci. Publ., Hackensack, NJ|title=Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures|year=2018}}</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 factor less than ''k''. 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 NP and in [[co-NP]] (and even in [[UP (complexity)|UP]] and co-UP<ref>[[Lance Fortnow]]. Computational Complexity Blog: [http://weblog.fortnow.com/2002/09/complexity-class-of-week-factoring.html Complexity Class of the Week: Factoring]. 13 September 2002.</ref>). If the problem is NP-complete, the polynomial time hierarchy will collapse to its first level (i.e., NP = co-NP). The most [[algorithmic efficiency|efficient]] known algorithm for integer factorization is the [[general number field sieve]], which takes expected time

:<math>O\left (\exp \left ( \left (\tfrac{64n}{9} \log(2) \right )^{\frac{1}{3}} \left ( \log(n\log(2)) \right )^{\frac{2}{3}} \right) \right )</math>

to factor an ''n''-bit integer. The best known [[quantum algorithm]] for this problem, [[Shor's algorithm]], runs in polynomial time, although this does not indicate where the problem lies with respect to non-[[quantum complexity theory|quantum complexity classes]].