Does every decision problem whose proposed solutions can be verified in
polynomial time also have a polynomial-time algorithm for finding a solution?
In complexity-class notation: prove or disprove P = NP.
This asks whether efficiently checking a certificate is fundamentally easier than efficiently finding one. It underlies the theory of NP-completeness and the security assumptions of much public-key cryptography.
Give precise definitions of deterministic polynomial time, nondeterministic polynomial time, polynomial-time reductions, and NP-completeness.
P consists of decision problems solved by a deterministic algorithm in time
bounded by a polynomial in the input length. NP consists of problems for
which a proposed “yes” certificate can be checked in polynomial time. The
question is whether these two classes are equal.
Thousands of problems are NP-complete, so a polynomial algorithm for one would put all of NP in P. Major lower-bound techniques face known barriers such as relativisation, natural proofs, and algebrisation. These are limits of methods, not proofs that the problem is unsolvable.
NP does not mean “not polynomial,” and it does not mean “non-polynomial.” It means nondeterministic polynomial-time verification. Hardness of a practical instance is not a proof of worst-case complexity separation.
SAT asks whether a Boolean formula has a satisfying assignment. A proposed
assignment is quickly verified, and the Cook--Levin theorem makes SAT
NP-complete. This makes SAT a natural focal point: a polynomial-time SAT
algorithm would establish P=NP.
Circuit lower bounds, proof complexity, communication complexity, algebraic complexity, and pseudorandomness are active approaches. Each studies a model or consequence of efficient computation; none currently proves the required unrestricted lower bound.
Reduce one standard NP problem to another, implement a brute-force SAT solver, and identify exactly where its running time becomes exponential.