更改

==Problems in NP not known to be in P or NP-complete==

==Problems in NP not known to be in P or NP-complete==

{{Main article|NP-intermediate|l1=NP-intermediate}}

{{Main article|NP-intermediate|l1=NP-intermediate}}

In 1975, [[Richard E. Ladner]] showed that if P ≠ NP then there exist problems in NP that are neither in P nor NP-complete.<ref name="Ladner75" /> <ref>R. E. Ladner "On the structure of polynomial time reducibility," ''[[wikipedia:Journal_of_the_ACM|Journal of the ACM]]'' 22, pp. 151–171, 1975. Corollary 1.1. [http://portal.acm.org/citation.cfm?id=321877&dl=ACM&coll=&CFID=15151515&CFTOKEN=6184618 ACM site].</ref>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.

In 1975, [[Richard E. Ladner]] showed that if P ≠ NP then there exist problems in NP that are neither in P nor NP-complete.<ref>R. E. Ladner "On the structure of polynomial time reducibility," ''[[wikipedia:Journal_of_the_ACM|Journal of the ACM]]'' 22, pp. 151–171, 1975. Corollary 1.1. [http://portal.acm.org/citation.cfm?id=321877&dl=ACM&coll=&CFID=15151515&CFTOKEN=6184618 ACM site].</ref>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.