Ladner's theorem

Ladner's theorem

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.


Search another word or see Ladner's theoremon Dictionary | Thesaurus |Spanish
Copyright © 2015, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature