monteverde

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
Axioms
propext, Classical.choice, Quot.sound
Independent check
nanoda: 16,507 declarations, no errors
Lean
v4.36.0-rc2
License
Apache-2.0

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.

Clay
Monteverde
cslib-frontier
Statements
ClayPVersusNP
NegativeBranch
Statements
CslibPEqNP
P encBits = NP encBits
Classes
InPolynomialTime
InNondeterministicPolynomialTime
PolynomialTimeReducible
Classes
P (blockEnc Γ)
NP (blockEnc Γ)
PolyTimeReducible
Functions
TM2ComputableInPolyTime e eo f
Functions
ComputableInPolyTime f
Encodings
words over Γ
w#y, certificates over Γ₁
Encodings
List Bool
encPair, 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 FinTM2 model 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.

CheckIt 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.

cslib-frontierCslibFrontier/Computability
49,439
descriptive-complexityPierreSenellart, incl. lax/ archive copies
31,938
starpos/lean-np-complete
5,467
CSLib
3,463
konard/p-vs-np
2,444

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 componentCommit
cslib-frontier9bfe667f8c66a8a2a3e17391ce9a5cc965190544
LeanMillenniumPrizeProblems (vendored)603053dc267cf3efe422f438eb78098c0ececd6f
millennium-cook-levin (vendored)879c4835640119ad009abeb62ebd7a96f87eb9e8
Mathlib (through cslib-frontier)bbff2954fe5ee3b7a4b33cc26ef873a1c3277d91