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
Classification
Statement Form StatementIf P is not equal to NP, then NP contains problems that are neither in P nor NP-complete. 1 Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
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.
Reader 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.