Every day, computers search: for a schedule that meets all constraints, a route that visits every city cheaply, a key that decrypts a message, a proof of a theorem. In each case a proposed solution is easy to check, but no method is known to find one that is essentially faster than trying all candidates. Whether checking is genuinely easier than finding is the P versus NP problem, the central open question of theoretical computer science and one of the seven Millennium Prize Problems of the Clay Mathematics Institute. Its official formulation is Stephen Cook's problem description, The P versus NP problem (2000), and this mission formalizes that document: the classes and exactly as Cook defines them, the conjecture as the goal, and the classical results Cook surveys as milestones.
Timeline.
Fix the alphabet . A string is a finite sequence of bits, in Lean PvsNP.Str = List Bool, and is its length. A language is a set , in Lean Language Bool. Cook notes (p. 2) that the problem does not depend on the alphabet, so long as it has at least two symbols.
The machine model is Mathlib's bundled multi-stack machine Turing.FinTM2: finitely many stacks, a finite program, a finite internal memory, and a finite input alphabet. A machine is started with the input string on its input stack; it halts in steps with output if after exactly executions of the step function it has stopped, its output stack holds , every other stack is empty and its memory is reset. Each step executes one program statement, a fixed finite tree of stack operations, so is within a constant factor of the number of elementary operations. A function is computable in polynomial time (PvsNP.PolyTimeDecider) if some machine, on every input , halts within steps with output , for a polynomial with natural coefficients; this is Mathlib's Turing.TM2ComputableInPolyTime. The same notion with output strings gives polynomial-time computable functions (PvsNP.PolyTimeComputable).
Following Cook (p. 2):
PvsNP.P) is the class of languages for which some polynomial-time computable satisfies for all .PvsNP.PolyTimeChecker) if the language is decided in polynomial time; here is coded (PvsNP.encodePair) by tagging the symbols of and of differently, so the input alphabet has four symbols and the machine sees the boundary, and .PvsNP.NP) is the class of languages for which there are and a polynomial-time checking relation withPvsNP.PReducible, Cook's Definition 3) if there is a polynomial-time computable with for all ; and is -complete (PvsNP.NPComplete, Definition 4) if and for every .PvsNP.E, Cook p. 9) is the class of languages decided by a machine whose step bound satisfies for all , for some constants .A CNF formula (PvsNP.CNF) is a list of clauses, a clause a list of literals, and a literal a pair meaning if and if . It is satisfiable (PvsNP.Satisfiable) if some assignment makes every clause contain a true literal. Formulas are coded as strings (PvsNP.encodeCNF) by two-bit blocks: for a data bit (sign, then the binary digits of ), for end of literal, for end of clause. SAT (PvsNP.SAT) is the set of codes of satisfiable formulas and 3-SAT (PvsNP.ThreeSAT) the set of codes of satisfiable formulas all of whose clauses have exactly three literals.
Cook's Problem Statement (p. 2) is "Does ?", and the prize is offered for either answer. The goal fixes the answer that Cook reports (p. 7) most complexity theorists believe:
that is, some language has a polynomial-time checking relation but no polynomial-time decision procedure. This is PvsNP.P_ne_NP. It is open; if were true the goal would be false, and its role is to fix in Lean the exact statement the prize asks about, so that the known results are formalized against the same definitions.
PvsNP.P_subset_NP; Cook p. 2, "trivial").PvsNP.mem_P_of_pReducible).PvsNP.npComplete_of_pReducible).PvsNP.P_eq_NP_of_npComplete_mem_P).PvsNP.sat_mem_NP; Cook p. 5).PvsNP.cook_levin; Cook p. 4–5).PvsNP.threeSAT_npComplete; Cook p. 5).PvsNP.P_ne_E): the time hierarchy theorem of Hartmanis and Stearns, the separation "we know exists and can prove" by diagonalization (Cook p. 7–9).PvsNP.ladner): if , some is neither in nor -complete.Two further items are not milestones: (PvsNP.P_eq_NP_iff_sat_mem_P), and the injectivity of the formula coding (PvsNP.encodeCNF_injective), which certifies that encodeCNF is a coding.
The result itself. says that for the thousands of -complete problems of scheduling, routing, packing, logic and algebra, no algorithm is essentially better than exhaustive search, and that the one-way functions on which public-key cryptography rests can exist. would, by Cook's Proposition 1(c), give polynomial-time algorithms for all of them at once, and would let a computer find any proof of reasonable length of any theorem (Cook p. 6).
Formalizing it. Mathlib contains the multi-stack machine model and the definition of polynomial-time computability (Spelier and van Gent, 2020) but essentially no theorems about them: even the composition of two polynomial-time machines is only a proof_wanted. None of the milestones has a Lean proof. The Cook–Levin theorem has a machine-checked proof in Coq (Gäher and Kunze, 2021); the time hierarchy theorem and Ladner's theorem have, to the extent known, no machine-checked proof in any system. Proving the milestones builds, in Lean, the basic toolkit of complexity theory: composition and pairing of machines, a universal machine with a step counter, and the encoding of a machine's computation as a CNF formula.
Both known methods for separating classes fail here. Diagonalization proves by simulating every polynomial-time machine and disagreeing with it, but every such argument relativizes, and Baker, Gill and Solovay give an oracle relative to which . Circuit lower bounds would suffice, since , but the best lower bound for the circuit size of any explicit Boolean function is linear in the number of inputs (Cook p. 8), and Razborov and Rudich show that every "natural" lower-bound technique would break the pseudorandom generators that are believed to exist. The newcomer's first idea, that verifying a certificate is "obviously" easier than finding one because there are exponentially many candidates, is not an argument: shows exponential search can be necessary in general, but nothing known rules out a clever polynomial-time algorithm for SAT; the best known runs in time about for 3-SAT (Cook p. 7).
The formalization has its own obstacle. Every milestone requires writing explicit multi-stack machines in Lean and bounding their running times; milestones 8 and 9 require a universal machine and a coding of machines as strings.
List Bool, languages Language Bool, and , , are Set (Language Bool); the goal is the inequality P ≠ NP of these sets.Polynomial.eval of a Polynomial ℕ for polynomial time; this is equivalent to Cook's bound . For the bound is for all , equivalent to Cook's .Bool ⊕ Bool), certificates are strings over the same alphabet with (with ), and the checker runs in time polynomial in .PvsNP.encodeCNF. In 3-SAT every clause has exactly three literals.No trivializing formalization. contains every finite language and every language in is decidable, so neither side of the goal is degenerate; the goal cannot be settled by the choice of machine model, which is polynomially equivalent to Turing machines.
Infrastructure needed and welcome contributions. Composition of polynomial-time machines (Mathlib's proof_wanted TM2ComputableInPolyTime.comp); machines for pairing, unpairing and copying strings; a universal multi-stack machine with a step counter, and a coding of machines as strings; the CNF tableau encoding of a bounded computation for the Cook–Levin theorem; a parser machine for encodeCNF. Theorems in the PvsNP namespace, decompositions of the milestones, and Mathlib lemmas about Turing.FinTM2 are all welcome.
namespace PvsNP theorem P_ne_NP : P ≠ NP := by sorry end PvsNP
Cook's Problem Statement (p. 2) reads: Does ? This theorem asserts the negative answer,
the class of languages over that are decided by some multi-stack machine within a polynomial number of steps is not the same as the class of languages that have a polynomial-time checking relation with polynomially bounded certificates. Since (Cook, p. 2; a milestone of this mission), the statement is equivalent to the existence of a language with a polynomial-time checking relation and an exponent such that for all , but with no polynomial-time decision procedure.
Cook (p. 7): "Most complexity theorists believe that ." The Millennium Prize is offered for a proof of either answer; this theorem is the conjectured one. It is open: a proof would settle the Millennium Prize Problem and, by Cook's Proposition 1(c), show that none of the -complete problems (Satisfiability, 3-SAT, Karp's 21 problems, and the hundreds catalogued since) has a polynomial-time algorithm. Its role in the mission is to fix in Lean the exact statement the prize asks about, so that the classical partial results (the milestones) are formalized against the same definitions.
Formalization Note P and NP are the sets of languages PvsNP.P, PvsNP.NP : Set (Language Bool) of the definition bundle, defined via Mathlib's Turing.TM2ComputableInPolyTime over the multi-stack machine model, which is polynomially equivalent to Turing machines. The statement is the inequality of these two sets. If is in fact true, this theorem is false; its negation is not an item of the mission.
No submissions yet on this mission's goal. Log in and be the first to prove it.