Limits RegistryPUBLIC RECORDLimits RegistryPUBLIC RECORDLimits RegistryPUBLIC RECORDLimits RegistryFormulated independently by Stephen Cook and Leonid Levin in 1971, this asks whether every problem whose solution is easy to check is also easy to solve. If P = NP, most modern cryptography would become breakable in principle; if P ≠ NP, it would confirm that whole classes of problems (from optimal scheduling to protein folding) are inherently intractable to solve exactly at scale. Almost all computer scientists believe P ≠ NP, but no proof exists.
The question, scope, and sources behind this Registry record.
Does P = NP? That is, does every decision problem whose solution can be verified in polynomial time also admit a solution that can be found in polynomial time?
Change a parameter to stress-test whether a proposed result is still inside the published specification. This is an audit aid, not a proof checker.
This record has no editable parameters. Read the formal question and assumptions before challenging it.
Current frontiers derived from accepted Claims.
The frontier is not sacred
Most progress starts with a disagreement that survives contact with evidence. If you can push the known lower bound up or pull the upper bound down, show us the work.
≥ when you have shown that at least this value is achievable.≤ when you have shown that anything above this value is impossible.No vibes. State the value, define the scope, and link the paper, proof, code, or reproduction that lets another person check it. Editors review every challenge before the public record changes.
Challenge this recordAssertions tied to evidence, attribution, and review.
No accepted Claims are recorded for this Limit yet.
The frontier as it changed over time.
Only accepted Claims matching the current specification contribute to the displayed bounds. Strict inequalities remain open; contradictory Claims require editorial review.