Ladner's Theorem, proved by Richard Ladner in 1975, states that if P does not equal NP then there exist problems in NP that are neither solvable in polynomial time nor NP-complete, a class of problems now called NP-intermediate. Ladner constructed an artificial problem with exactly this property under the assumption that P does not equal NP, establishing that P equals NP precisely when no such intermediate problems exist, though whether any naturally occurring problem, such as graph isomorphism, actually belongs to this class remains an open question.
Facts
StatementIf P is not equal to NP, then NP contains problems that are neither in P nor NP-complete. 1 Classification
Statement Form Connections
Has Statement Form
In Branch
Source NP-intermediate (Wikipedia)
In the Other Atlases
Credited To
Also in Computing Atlas: credited with this subject.
Sources
1. Ladner's theorem, Wikipedia
Lead paragraphQuote, Lead paragraph
If P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete.
2. NP-intermediate (Wikipedia)
Lead
NPI. Ladner's theorem, shown in 1975 by Richard E. Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete.
In Branch: Computational Complexity Theory, Lead paragraph
In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI.
In Group: Computability and Complexity Theory, Lead section
In computational complexity, problems that are in the complexity class NP
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.