Ladner's theorem
From Wikipedia, the free encyclopedia
In computational complexity, Ladner's theorem asserts that, if the computational classes P and NP are not equal, the latter contains problems that are neither in P nor NP-complete.
Problems that are in NP but are neither in P nor NP-complete are sometimes called NP-intermediate. Ladner's theorem exhibits a problem that is NP-intermediate provided that P is not equal to NP. The problem it exhibits is defined ad-hoc for the proof and is otherwise uninteresting. It is an open question whether any "natural" problem has the same property; some problems that are considered good candidates for being NP-intermediate if P is not equal to NP are the graph isomorphism problem, factoring, and computing the discrete logarithm.
[edit] References
- Ladner, Richard (1975). "On the Structure of Polynomial Time Reducibility". Journal of the ACM (JACM) 22 (1): 155–171. doi:.
- Basic structure, Turing reducibility and NP-hardness
- Two Proofs of Ladner’s Theorem
- NP completeness
