Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

CookLevin Complexity Classes P and NP

Definition
CookLevin_Complexity

by Rizwan G Mir · Sep 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-classeskarp-reductionp-vs-np

Definitions of computational complexity classes P and NP, verifiers (IsNPVerifier, VerifierMachine), Karp reductions (PolyReducible, <=p), NPHard, and NPComplete.

Definition code
import Definitions.Def_CookLevin_Satisfiability
import Definitions.Def_CookLevin_Cost
set_option autoImplicit true
/-
  CookLevinLean/Complexity.lean

  Computability, the complexity classes P and NP, and Karp reductions.

  Every notion below is defined against the cost model of
  `CookLevinLean.Cost`: a *step* is one application of `exe`, and a bound is a
  bound on the number of steps the interpreter `execute` is run for.  None of
  these definitions bounds only the length of an output or of a witness --
  that was the defect of the previous version of this file, which made
  `IsPolyTimeComputable f` true of every function with short output (including
  uncomputable ones) and `IsNPVerifier V` true of every predicate with short
  witnesses.
-/




namespace CookLevin

/-- Membership of a string `x` in language `L`. -/
def InLang (x : List Bool) (L : Language) : Prop := L x

/-- `f` is computable in polynomial time: some multi-tape Turing machine
computes `f` and **halts within `c * (n+1)^d` steps** on every input of
length `n`. -/
def IsPolyTimeComputable (f : List Bool → List Bool) : Prop :=
  ∃ (M : Machine) (k G c d : Nat),
    TuringMachine k G M ∧
    ComputesInTime M k (polyBound c d) f

/-- Polynomial-time many-one (Karp) reduction from `L₁` to `L₂`. -/
def PolyReducible (L₁ L₂ : Language) : Prop :=
  ∃ f : List Bool → List Bool,
    IsPolyTimeComputable f ∧ ∀ x : List Bool, InLang x L₁ ↔ InLang (f x) L₂

infix:50 " ≤p " => PolyReducible

/-- `V` is decided by some multi-tape Turing machine **within
`c * (|x|+|w|+1)^d` steps**, with `x` on tape `0` and `w` on tape `1`.

This isolates the one ingredient of `IsNPVerifier` that is about *implementing*
a decision procedure, as opposed to its input/output behaviour. -/
def PolyTimeDecidable (V : List Bool → List Bool → Bool) : Prop :=
  ∃ (M : Machine) (k G c d : Nat),
    TuringMachine k G M ∧
    ∀ x w : List Bool,
      DecidesIn M k (boolsToSymbols x) (boolsToSymbols w)
        (polyBound c d (x.length + w.length)) (V x w)

/-- `V` is a polynomial-time verifier: it is decided by a machine running in
polynomially many *steps*, and it only accepts certificates of length at most
`polyBound c d |x|`.

This is the textbook definition, with `≤` rather than `=`: no normal-form
assumption is made anywhere in this development, and the reduction of
`CookLevinLean/Reduction.lean` handles certificates of every length up to the
bound (see `blankSuffixClauses` there). -/
def IsNPVerifier (c d : Nat) (V : List Bool → List Bool → Bool) : Prop :=
  PolyTimeDecidable V ∧
    ∀ x w : List Bool, V x w = true → w.length ≤ polyBound c d x.length

/-- The data exhibited by `PolyTimeDecidable`, packaged so that a proof of
`InNP L` hands the Cook-Levin reduction an *actual machine* to build a tableau
for.  This is what lets `cook_levin_nphard` construct its reduction without
ever consulting `L` itself. -/
structure VerifierMachine (V : List Bool → List Bool → Bool) where
  /-- The machine computing the verdict. -/
  M : Machine
  /-- Its number of tapes. -/
  k : Nat
  /-- Its alphabet size. -/
  G : Nat
  /-- Leading coefficient of the time bound. -/
  c : Nat
  /-- Degree of the time bound. -/
  d : Nat
  /-- `M` is a well-formed `k`-tape machine over an alphabet of size `G`. -/
  wf : TuringMachine k G M
  /-- `M` decides `V` within the step bound. -/
  decides : ∀ x w : List Bool,
    DecidesIn M k (boolsToSymbols x) (boolsToSymbols w)
      (polyBound c d (x.length + w.length)) (V x w)

theorem PolyTimeDecidable.nonempty {V : List Bool → List Bool → Bool}
    (h : PolyTimeDecidable V) : Nonempty (VerifierMachine V) := by
  obtain ⟨M, k, G, c, d, hwf, hdec⟩ := h
  exact ⟨⟨M, k, G, c, d, hwf, hdec⟩⟩

theorem VerifierMachine.polyTimeDecidable {V : List Bool → List Bool → Bool}
    (vm : VerifierMachine V) : PolyTimeDecidable V :=
  ⟨vm.M, vm.k, vm.G, vm.c, vm.d, vm.wf, vm.decides⟩

/-- Membership of `L` in NP: a polynomial-time verifier whose accepted
certificates characterise `L`. -/
def InNP (L : Language) : Prop :=
  ∃ (V : List Bool → List Bool → Bool) (c d : Nat),
    IsNPVerifier c d V ∧ ∀ x : List Bool, InLang x L ↔ ∃ w : List Bool, V x w = true

/-- `L` is NP-hard if every language in NP polynomial-time reduces to it. -/
def NPHard (L : Language) : Prop :=
  ∀ L' : Language, InNP L' → L' ≤p L

/-- `L` is NP-complete if it is in NP and NP-hard. -/
def NPComplete (L : Language) : Prop := InNP L ∧ NPHard L

end CookLevin
Source
https://github.com/Rizvonium/cook_levin_lean_v1/blob/main/CookLevinLean/Complexity.lean
Human review
  • Endorsed by Community (Bot) · Oct 4, 2026

  • Endorsed by wurtle · Oct 4, 2026

    Confirmed by the mission captain (proposal self-audit).

  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me