The Clay P vs NP statement and P vs NP in cslib-frontier are equivalent.
Monteverde proves in Lean 4 that the LeanMillenniumPrizeProblems formulation of the Clay P vs NP statement is equivalent to P vs NP in cslib-frontier, the largest Lean complexity library. It does not resolve P vs NP. It connects the two statements, so that a Lean result about one is a Lean result about the other.
-- Monteverde/Statements/Defs.lean
def CslibPEqNP : Prop :=
∀ {α : Type} (enc : α ↪ List Bool), Cslib.Complexity.P enc = Cslib.Complexity.NP enc
-- Monteverde/Headline/
theorem clay_iff_cslib : Millennium.ClayPVersusNP ↔ CslibPEqNP
theorem clay_negative_iff_cslib :
Millennium.ClayPVersusNP.Formulations.NegativeBranch ↔ ¬ CslibPEqNP
theorem cslibPEqNP_iff_bits : CslibPEqNP ↔ P encBits = NP encBits
Two definitions of P and NP
Both libraries build on Mathlib, but they define P and NP in different ways. Monteverde proves that the differences do not matter: the classes agree, so the two P = NP statements agree.
Clay
As LeanMillenniumPrizeProblems formalizes Cook's problem description. Mathlib's multi-stack Turing machine FinTM2. Inputs are words over any
finite alphabet. NP uses Cook's checking relation: certificates over any finite
alphabet, with length at most |w|^k, checked on the pair word
w#y.
ClayPVersusNP says P = NP for every alphabet with at
least two symbols.
cslib-frontier
A binary multi-tape Turing machine. Inputs are any type with an injective binary
encoding enc : α ↪ List Bool. NP uses a Boolean verifier with binary
certificates of length exactly p(n).
cslib-frontier has no named P = NP proposition. Its theorems state it for every
encoding, so CslibPEqNP takes that form.
The bridge
Four layers connect the two sides. Each layer uses only the layers under it, and each link is a Lean theorem.
NegativeBranch
clay_iff_cslibclay_negative_iff_cslibP encBits = NP encBits
InNondeterministicPolynomialTime
PolynomialTimeReducible
clayP_iff_cslibclayNP_iff_cslibclayReducible_iff_cslibNP (blockEnc Γ)
PolyTimeReducible
tm2_iff_computableInPolyTime_wordsw#y, certificates over Γ₁
blockEncpairWordcertDecoderencPair, binary certificates
How the proof works
About 2,100 lines of new Lean, in Monteverde/.
Encodings
The block code writes the symbol with index i as the bits
(1 1)^i 0, and a word as the concatenation of its symbols. Clay's pair
word w#y converts to encPair and back in polynomial time.
A new total decoder reads certificates over any finite alphabet.
Functions
Forward: Mathlib's FinTM2 makes only the input alphabet finite. A push
writes a function of the finite state, so only finitely many symbols can reach a
stack; Monteverde restricts the stacks to them, then applies cslib-frontier's bridge.
Reverse: a recoder, cslib-frontier's compiler and a decoder run in sequence, joined
by the TM2 composition theorem from millennium-cook-levin.
Classes
P follows from the function bridge. For NP, the cslib-frontier verifier decodes a
Clay certificate and runs the Clay checker, and padding fixes the length. The other
way, Clay certificates are bits, and the bound |w|^k covers the
verifier's length once |w| ≥ 2. Words of length 0 and 1 use a lookup
table.
Statements
From Clay: apply the Clay statement at the alphabet Bool to the binary
image of SAT, then use cslib-frontier's Cook-Levin theorem to get P = NP for every
encoding. To Clay: for each alphabet Γ, use the encoding
blockEnc Γ and the class bridges.
Use it
A Lean result on one side now transfers to the other. These examples are checked in CI.
import Monteverde
-- A cslib-frontier proof of P = NP on binary strings gives the Clay statement.
example (h : P encBits = NP encBits) : Millennium.ClayPVersusNP :=
clay_iff_cslib.mpr (cslibPEqNP_iff_bits.mpr h)
-- A problem in cslib-frontier NP but not in P gives the negative Clay statement.
example {α : Type} (enc : α ↪ List Bool) (A : Set α) (hNP : A ∈ NP enc) (hP : A ∉ P enc) :
Millennium.ClayPVersusNP.Formulations.NegativeBranch :=
clay_negative_iff_cslib.mpr fun h => hP (by rw [h enc]; exact hNP)
- The theorems do not resolve P vs NP.
- They do not prove that Mathlib's
FinTM2model agrees with Cook's one-tape Turing machine. That is a choice of the LeanMillenniumPrizeProblems formulation, and the result is about that formulation.
What you must trust
Lean checks every proof, so the risk is a wrong statement. To trust the result, read four short statement files, the vendored Clay definitions, and cslib-frontier's definitions of P and NP. You do not need to read the proofs.
| Check | It fails when |
|---|---|
| Exact types Audit/ClaimCheck.lean | A main theorem is renamed or its type changes. |
| Axioms Audit/Axioms.lean | A theorem uses an axiom other than propext, Classical.choice, Quot.sound. A sorry fails too. |
| Statement isolation Audit/Isolation.lean | A statement file imports a proof, or a theorem's type is not exactly its statement, term for term. |
| Vendored files scripts/diff_vendor.sh | The vendored Clay file differs from upstream by an unlisted change. |
| Independent kernel check scripts/kernel_check.sh | nanoda, a Lean type checker written in Rust, rejects the exported proofs. |
| Non-vacuity Tests/NonVacuity.lean | A simple language is not in P, SAT is not in NP, or the halting problem is in NP, on either side. |
| Cook-Levin cross-check CrossCheck/CookLevin.lean | The two independent Lean proofs of Cook-Levin do not transfer through the bridge. Today each library's SAT is NP-complete for the other library's definitions. |
A line-by-line audit maps Cook's official Clay problem description to the Lean definitions.
The largest Lean complexity library
Theorem and lemma declarations in each public Lean complexity library, counted in full clones at pinned commits on November 22, 2026.
Full table and method: Audit/size_table.md.
Build it
You need elan.
git clone https://github.com/wbnns/monteverde && cd monteverde
lake exe cache get # Mathlib build cache
lake build Vendor Monteverde Audit Tests # the proofs and their checks
lake env lean Audit/Axioms.lean # print the axioms
| Pinned component | Commit |
|---|---|
| cslib-frontier | 9bfe667f8c66a8a2a3e17391ce9a5cc965190544 |
| LeanMillenniumPrizeProblems (vendored) | 603053dc267cf3efe422f438eb78098c0ececd6f |
| millennium-cook-levin (vendored) | 879c4835640119ad009abeb62ebd7a96f87eb9e8 |
| Mathlib (through cslib-frontier) | bbff2954fe5ee3b7a4b33cc26ef873a1c3277d91 |