STRATA
Skip to study
XLVII

Computational complexity

P versus NP

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.

Identify what a complete argument must establish.

  1. For equality, supply a correct algorithm and polynomial bound for every input of an NP-complete problem such as SAT.
  2. 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.
  3. 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.

  1. 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.

  2. Oracle constructions expose a proof-method limitation.

    Baker, Gill and Solovay construct oracle worlds with opposite answers to P versus NP.

  3. Natural proofs identify a conditional circuit barrier.

    Razborov and Rudich study properties that are large, efficiently recognizable from truth tables, and useful for lower bounds.

  4. Algebrization refines the oracle boundary.

    Aaronson and Wigderson show that low-degree algebraic access still cannot resolve several central separations.

Separate established results from the remaining claim.

Inspect the upstream dependencies.

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.

Work through a restricted calculation.

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.

Compare this example with the interactive proof diagnostics

Follow the downstream consequences conditionally.

Locate the actual quantum connection.

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.

Follow quantum mechanics through the historical map

Inspect the supporting sources.

  1. The Millennium Prize Problems

    Clay Mathematics Institute · Current official categories and original seven-prize fund.

  2. The P versus NP Problem

    Stephen Cook / Clay Mathematics Institute · Classical deterministic computation, polynomial certificates and exact decision question.

  3. Relativizations of the P = ? NP Question

    Theodore Baker, John Gill and Robert Solovay / SIAM Journal on Computing · 1975 opposite oracle outcomes and the relativization barrier.

  4. Natural Proofs

    Alexander Razborov and Steven Rudich / Journal of Computer and System Sciences · Constructivity, largeness and usefulness; conditional barrier based on pseudorandomness assumptions.

  5. Algebrization: A New Barrier in Complexity Theory

    Scott Aaronson and Avi Wigderson / STOC 2008 · Low-degree oracle extensions and limitations on algebrizing techniques.

  6. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

    Peter W. Shor / arXiv · Quantum polynomial-time algorithms for factoring and discrete logarithms, announced at FOCS 1994.