P versus NP
If a proposed solution can be checked efficiently, can a solution always be found efficiently?
Progress records 0
Understand the problem ↓0 records · How we rate progress
No curated contributions yet. You can follow this interest for future updates.
Understanding the problem
Read the background
If a proposed solution can be checked efficiently, can a solution always be found efficiently? P versus NP asks whether these two classes of decision problems coincide.
P is the class of decision problems solvable in polynomial time. NP is the class whose yes answers have certificates checkable in polynomial time. The question is whether these classes are equal. Efficiently solving one NP-complete problem in the worst case would establish P = NP.
A fast solver on many observed examples does not establish a polynomial-time bound for every input. Conversely, the failure of particular algorithms does not establish P ≠ NP. A proof must concern the mathematical model and the full class of inputs, rather than a model’s practical success rate.
Why it matters
The question shapes computational complexity, optimization, and cryptography.
What counts as progress
A valid resolution, a meaningful theorem about the problem or its barriers, or a clearly scoped formalization. Solving examples or improving a heuristic does not resolve P versus NP.
What to watch for
- For claimed algorithms, require correctness and a worst-case complexity analysis, including input encoding.
- For lower bounds or barriers, name the computational model and the exact class covered.
- Treat formalization as scoped progress: checking a restatement or special case is different from resolving the question.
Background review: 2026-10-11. Selected sources:
Website timeline
Publication dates and editorial changes.
No publication events yet.