Does every decision problem with efficiently verifiable certificates also have an efficient classical algorithm for finding the answer?
Clay: Unsolved
Status and source review: 2026-11-19
State the mathematical question precisely.
P contains languages decided by a deterministic Turing machine in polynomial worst-case time. NP contains languages admitting polynomial-length witnesses checked in polynomial time. Establish P = NP or P ≠ NP in this ordinary classical model.
For equality, supply a correct algorithm and polynomial bound for every input of an NP-complete problem such as SAT.
For separation, rule out every deterministic polynomial-time algorithm for at least one language in NP; a slow solver or hard benchmark family is insufficient.
Track input encoding and bit complexity. A primitive operation that hides exponential precision, memory or advice does not establish the required runtime.
Trace the results that changed the problem.
Cook and Levin make verification central.
NP-completeness links apparently different search and decision problems through polynomial reductions. Cook's publication appeared in 1971; Levin's independent work appeared in 1973.
Separate established results from the remaining claim.
Relativizing arguments cannot settle the original question.
An argument valid uniformly with arbitrary common oracles would contradict one of the opposite oracle examples. This limits a class of techniques, rather than proving independence from standard axioms.
Under the relevant strong pseudorandomness hardness assumption, a constructive, large property cannot prove superpolynomial lower bounds for general circuits. Omitting the assumption changes the theorem.
Arithmetic structure alone does not guarantee escape.
Algebrization captures many methods that surpass ordinary relativization. A candidate proof needs an identified step outside the applicable barrier, not merely algebraic notation.
Make each proposed approach answer for its obstacle.
These are research directions and diagnostic tests. Their inclusion does not establish novelty, feasibility at full scale, or a solution.
Audit a candidate algorithm before scaling it.
Write a correctness invariant and count operations in terms of the binary input length. Include branching, numerical precision, preprocessing and the cost of recognizing failure.
Obstacle. Average-case success can hide rare exponential cases. Replacing a difficult subproblem with an oracle merely relocates the difficulty.
Try the next discriminating test.
Search for an adversarial input family that breaks the invariant or makes a purportedly bounded parameter grow. A counterexample can invalidate a specific algorithm without settling P versus NP.
Use restricted lower bounds to test a proof idea.
State the exact circuit class or proof system first, then test whether the proposed invariant is useful, large or constructive in the relevant formal sense.
Obstacle. A separation for bounded depth, monotone circuits or a chosen proof system does not automatically extend to unrestricted polynomial computation.
Try the next discriminating test.
Document the first lemma requiring a restricted gate set; attempt a counterexample after adding one missing operation. Treat any surviving extension as a research lead pending a proof.
An exponential search space can encode a linear-time problem.
Let F_n = x₁ ∧ x₂ ∧ … ∧ x_n. Enumerate assignments in increasing binary order, so the sole satisfying assignment is last.
For n = 4, 8, 12, direct enumeration visits 16, 256, 4096 assignments respectively. Yet reading the n unit clauses immediately supplies the all-true witness in O(n) work.
The calculation disproves the inference that 2^n possible assignments force every algorithm to take exponential time. It is not a SAT lower bound.
Polynomially checkable discrete optimization and search tasks can often be solved through decision-to-search reductions. Polynomial degree and constants still determine practical usefulness.
Some verifiable tasks lack polynomial worst-case classical algorithms. This alone does not prove average-case hardness or the security of a particular cryptosystem.
Shor's algorithm gives quantum polynomial-time factoring and discrete logarithms. Its computational model differs from deterministic classical P, and these algorithms do not settle classical P versus NP. Quantum simulation speedups must be described through their own input and output costs.
Alexander Razborov and Steven Rudich / Journal of Computer and System Sciences · Constructivity, largeness and usefulness; conditional barrier based on pseudorandomness assumptions.