IDE
Sign in
Computational complexity Millennium Prize Problem Status: Open Status last verified

P versus NP

If a proposed answer can be checked quickly, can it also be found quickly? Formally: is every problem in NP also in P?

Problem statement

Is P = NP? The precise definitions (Turing machines, polynomial time, the classes P and NP) are in Cook's official problem description.

P  = { L : some deterministic TM decides L in time O(n^k) }
NP = { L : x ∈ L ⇔ ∃ certificate y, |y| ≤ poly(|x|), checkable in poly time }

Question: P = NP ?

Source: Stephen Cook — The P versus NP Problem (official problem description)

Introduction

Checking a filled-in Sudoku is easy; filling in a hard one seems to require search. P is the class of decision problems a computer can solve in time polynomial in the input size. NP is the class whose "yes" answers have a certificate that can be checked in polynomial time.

Every problem in P is in NP. The question is whether the converse holds. Cook (1971) and Levin showed that Boolean satisfiability (SAT) is NP-complete: a polynomial-time algorithm for SAT would give one for every NP problem.

It is one of the Clay Millennium Prize Problems. Most researchers expect P ≠ NP, but that expectation is not a proof.

Definitions

NP-complete
A problem in NP to which every NP problem reduces in polynomial time. SAT, 3-SAT, graph 3-colouring and the decision version of the travelling salesman problem are examples.
Polynomial-time reduction
A polynomial-time transformation of instances of one problem into instances of another that preserves the answer.

What is known

Each statement says how certain it is: an established (proved) result, an experimental observation, an open conjecture, or an unverified claim.

  • Established result SAT is NP-complete (Cook, 1971; Levin independently). [Stephen A. Cook]
  • Established result Proof barriers: relativizing techniques (Baker, Gill and Solovay, 1975) and "natural proofs" (Razborov and Rudich) cannot settle the question on their own. [Stephen Cook]
  • Experimental observation Modern SAT solvers handle many large industrial instances quickly. This says nothing about the worst case, which is what P versus NP is about.
  • Open conjecture P ≠ NP (widely believed; unproven). [Stephen Cook]

Important limitations

  • Solving many instances fast, or failing to, proves nothing about all instances.
  • An algorithm that is fast on random or benchmark inputs is not a polynomial-time algorithm unless its worst-case bound is proved.
  • Any claimed proof must explain how it avoids the known barriers.

Status history

  1. Status: Open Named one of the seven Millennium Prize Problems by the Clay Mathematics Institute.
  2. Status: Open Checked against the Clay Mathematics Institute page: still unsolved.

This status is maintained by the Zerethon IDE team from authoritative sources. Contributions, runs and AI answers never change it.