$P$ versus $NP$

This is the central open problem of computational complexity: does the class $P$ of decision problems solvable in deterministic polynomial time coincide with the class $NP$ of problems whose yes-instances admit short certificates checkable in polynomial time? The question was given its modern form by Cook in 1971, who proved that Boolean satisfiability is $NP$-complete, so that a polynomial-time algorithm for this single problem would yield one for all of $NP$ [Cook1971]. Karp then showed that the same completeness phenomenon pervades combinatorics, exhibiting a list of natural complete problems [Karp1972].

Since then thousands of problems across mathematics, optimization and the sciences have been shown $NP$-complete, and the near-universal expectation is that $P\ne NP$. Yet no unconditional superpolynomial lower bound has been proved for any of them in the general deterministic Turing machine model, and known barrier results indicate that relativizing arguments and natural circuit-lower-bound techniques cannot by themselves settle the question [Cook2006PvsNP].

The problem remains open in both directions: a resolution requires either a polynomial-time algorithm for some $NP$-complete problem or a proof that none exists.