Added to Favorites

Related Searches

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.## References

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.

- Ladner, Richard (1975). "On the Structure of Polynomial Time Reducibility".
*Journal of the ACM (JACM)*22 (1): 155–171. - Basic structure, Turing reducibility and NP-hardness
- Two Proofs of Ladner’s Theorem
- NP completeness

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday May 28, 2008 at 11:18:19 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday May 28, 2008 at 11:18:19 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.