Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_lautemann_bridge

Definition

by Henry Yuen · Jul 24, 2026 · Mathlib c5ea003 (Lean v4.30.0)

bppcomplexity-theorycountingpolynomial-hierarchy

A sorry-free formal library for the amplified-verifier-to-Sigma₂ bridge: translation tuple encoding and decoding, exact shifted-cover semantics, polynomial witness bounds, the small- and large-cover arithmetic, eventual domination of polynomials by powers of two, finite-length exceptions, and the full Sigma₂ characterization conditional only on the long-input shifted-OR decider.

Definition code
import Definitions.Def_sipser_gacs_lautemann
import Definitions.Def_sgl_verifier_constructions
import Mathlib.Logic.Equiv.Fin.Basic
import Mathlib.Data.Nat.Basic
import Mathlib.Data.List.GetD
import Mathlib.Data.Fintype.BigOperators
import Mathlib.Analysis.SpecificLimits.Normed
import Definitions.Def_sgl_finite_override_delegate

namespace SipserGacsLautemann

def coverShiftCount (randomBits : Nat) : Nat :=
  randomBits + 1

def coverExistentialBits (randomBits : Nat) : Nat :=
  coverShiftCount randomBits * randomBits

def decodeCoverTranslation (randomBits : Nat) (encoded : List Bool)
    (i : Fin (coverShiftCount randomBits)) : List Bool :=
  List.ofFn fun j : Fin randomBits =>
    encoded.getD (i.val * randomBits + j.val) false

def coverVerifier (randomBits : Nat)
    (verifier : List Bool → List Bool → Bool)
    (input existential universal : List Bool) : Bool :=
  decide (∃ i : Fin (coverShiftCount randomBits),
    verifier input
      (List.zipWith (· != ·) universal
        (decodeCoverTranslation randomBits existential i)) = true)

def encodeCoverTranslations {randomBits : Nat}
    (translations : Fin (coverShiftCount randomBits) → BitString randomBits) :
    BitString (coverExistentialBits randomBits) :=
  fun z =>
    let ij := finProdFinEquiv.symm z
    translations ij.1 ij.2

def unpackCoverTranslations {randomBits : Nat}
    (encoded : BitString (coverExistentialBits randomBits)) :
    Fin (coverShiftCount randomBits) → BitString randomBits :=
  fun i j => encoded (finProdFinEquiv (i, j))

theorem encodeCoverTranslations_unpack {randomBits : Nat}
    (encoded : BitString (coverExistentialBits randomBits)) :
    encodeCoverTranslations (unpackCoverTranslations encoded) = encoded := by
  funext z
  change encoded (finProdFinEquiv (finProdFinEquiv.symm z)) = encoded z
  rw [Equiv.apply_symm_apply]

theorem decodeCoverTranslation_encode {randomBits : Nat}
    (translations : Fin (coverShiftCount randomBits) → BitString randomBits)
    (i : Fin (coverShiftCount randomBits)) :
    decodeCoverTranslation randomBits
        (encodeCoverTranslations translations).toList i =
      (translations i).toList := by
  apply List.ext_get
  · simp [decodeCoverTranslation, BitString.toList]
  · intro n h₁ h₂
    simp only [decodeCoverTranslation, BitString.toList, List.get_eq_getElem,
      List.getElem_ofFn]
    have hn : n < randomBits := by
      simpa [BitString.toList] using h₂
    have hindex :
        i.val * randomBits + n <
          coverExistentialBits randomBits := by
      simp only [coverExistentialBits, coverShiftCount]
      calc
        i.val * randomBits + n <
            i.val * randomBits + randomBits :=
          Nat.add_lt_add_left hn _
        _ = (i.val + 1) * randomBits := by
          simp [Nat.add_mul]
        _ ≤ (randomBits + 1) * randomBits :=
          Nat.mul_le_mul_right randomBits (Nat.succ_le_iff.mpr i.isLt)
    have hindex' :
        i.val * randomBits + n <
          (List.ofFn (encodeCoverTranslations translations)).length := by
      simpa [BitString.toList] using hindex
    rw [List.getD_eq_getElem _ _ hindex']
    simp only [List.getElem_ofFn]
    change
      encodeCoverTranslations translations
          ⟨i.val * randomBits + n, hindex⟩ =
        translations i ⟨n, hn⟩
    have hflat :
        (⟨i.val * randomBits + n, hindex⟩ :
            Fin (coverExistentialBits randomBits)) =
          finProdFinEquiv (i, ⟨n, hn⟩) := by
      apply Fin.ext
      simp [finProdFinEquiv, Nat.add_comm, Nat.mul_comm]
    rw [hflat]
    simp [encodeCoverTranslations]

theorem zipWith_xor_toList {n : Nat} (x y : BitString n) :
    List.zipWith (· != ·) x.toList y.toList =
      (xor x y).toList := by
  apply List.ext_get
  · simp [BitString.toList]
  · intro i h₁ h₂
    simp [BitString.toList, xor]

theorem coverVerifier_encode_iff {randomBits : Nat}
    (verifier : List Bool → List Bool → Bool)
    (input : List Bool)
    (translations : Fin (coverShiftCount randomBits) → BitString randomBits)
    (point : BitString randomBits) :
    coverVerifier randomBits verifier input
        (encodeCoverTranslations translations).toList point.toList = true ↔
      ∃ i : Fin (coverShiftCount randomBits),
        verifier input (xor point (translations i)).toList = true := by
  simp only [coverVerifier, decide_eq_true_eq]
  apply exists_congr
  intro i
  rw [decodeCoverTranslation_encode, zipWith_xor_toList]

theorem coverVerifier_toList_iff {randomBits : Nat}
    (verifier : List Bool → List Bool → Bool)
    (input : List Bool)
    (encoded : BitString (coverExistentialBits randomBits))
    (point : BitString randomBits) :
    coverVerifier randomBits verifier input
        encoded.toList point.toList = true ↔
      ∃ i : Fin (coverShiftCount randomBits),
        verifier input
          (xor point (unpackCoverTranslations encoded i)).toList = true := by
  simpa only [encodeCoverTranslations_unpack] using
    (coverVerifier_encode_iff verifier input
      (unpackCoverTranslations encoded) point)

theorem polynomiallyBounded_coverExistentialBits
    {randomBits : Nat → Nat}
    (hrandomBits : PolynomiallyBounded randomBits) :
    PolynomiallyBounded
      (fun n => coverExistentialBits (randomBits n)) := by
  rcases hrandomBits with ⟨coefficient, degree, hbound⟩
  refine
    ⟨(coefficient + 1) * (coefficient + 1), degree + degree, ?_⟩
  intro n
  let power := (n + 1) ^ degree
  have hpower : 1 ≤ power := by
    exact Nat.one_le_pow' degree n
  have hr : randomBits n ≤ coefficient * power :=
    hbound n
  have hr' : randomBits n ≤ (coefficient + 1) * power :=
    hr.trans (Nat.mul_le_mul_right power (Nat.le_succ coefficient))
  have hrsucc : randomBits n + 1 ≤ (coefficient + 1) * power := by
    calc
      randomBits n + 1 ≤ coefficient * power + power :=
        Nat.add_le_add hr hpower
      _ = (coefficient + 1) * power := by
        simp [Nat.add_mul]
  calc
    coverExistentialBits (randomBits n) =
        (randomBits n + 1) * randomBits n := rfl
    _ ≤ ((coefficient + 1) * power) *
          ((coefficient + 1) * power) :=
      Nat.mul_le_mul hrsucc hr'
    _ = ((coefficient + 1) * (coefficient + 1)) *
          (n + 1) ^ (degree + degree) := by
      simp only [power, pow_add]
      ac_rfl

theorem card_bitString (n : Nat) :
    Fintype.card (BitString n) = 2 ^ n := by
  rw [Fintype.card_pi_const, Fintype.card_bool]

theorem acceptingCard_add_rejectingCard
    (verifier : List Bool → List Bool → Bool)
    (input : List Bool) (randomBits : Nat) :
    acceptingCard verifier input randomBits +
        rejectingCard verifier input randomBits =
      Fintype.card (BitString randomBits) := by
  classical
  unfold acceptingCard rejectingCard
  let p : BitString randomBits → Prop :=
    fun random => verifier input random.toList = true
  have hpartition :=
    Finset.card_filter_add_card_filter_not
      (s := (Finset.univ : Finset (BitString randomBits))) p
  rw [show
      (Finset.univ.filter fun random : BitString randomBits =>
        verifier input random.toList = false) =
        Finset.univ.filter fun random => ¬p random by
      ext random
      simp only [Finset.mem_filter, Finset.mem_univ, true_and, p]
      cases verifier input random.toList <;> simp]
  exact hpartition

theorem largeCoverArithmetic (inputLength randomBitCount bad : Nat)
    (herror :
      2 ^ (inputLength + 1) * bad ≤ 2 ^ randomBitCount) :
    2 ^ randomBitCount * bad ^ (randomBitCount + 1) <
      (2 ^ randomBitCount) ^ (randomBitCount + 1) := by
  by_cases hbad : bad = 0
  · subst bad
    have hpositive :
        0 < (2 ^ randomBitCount) ^ (randomBitCount + 1) :=
      Nat.pow_pos (Nat.pow_pos (by decide : 0 < (2 : Nat)))
    simpa using hpositive
  have hbadPow : 0 < bad ^ (randomBitCount + 1) :=
    Nat.pow_pos (Nat.pos_of_ne_zero hbad)
  have hexponent :
      randomBitCount <
        (inputLength + 1) * (randomBitCount + 1) := by
    calc
      randomBitCount < randomBitCount + 1 :=
        Nat.lt_succ_self randomBitCount
      _ = 1 * (randomBitCount + 1) := by simp
      _ ≤ (inputLength + 1) * (randomBitCount + 1) :=
        Nat.mul_le_mul_right (randomBitCount + 1)
          (Nat.succ_le_succ (Nat.zero_le inputLength))
  have hpower :
      2 ^ randomBitCount <
        (2 ^ (inputLength + 1)) ^ (randomBitCount + 1) := by
    rw [← pow_mul]
    exact
      (Nat.pow_lt_pow_iff_right (by decide : 1 < (2 : Nat))).2
        hexponent
  calc
    2 ^ randomBitCount * bad ^ (randomBitCount + 1) <
        (2 ^ (inputLength + 1)) ^ (randomBitCount + 1) *
          bad ^ (randomBitCount + 1) :=
      Nat.mul_lt_mul_of_pos_right hpower hbadPow
    _ = (2 ^ (inputLength + 1) * bad) ^
          (randomBitCount + 1) := by
      rw [mul_pow]
    _ ≤ (2 ^ randomBitCount) ^ (randomBitCount + 1) :=
      Nat.pow_le_pow_left herror _

theorem smallCoverArithmetic (inputLength randomBitCount good : Nat)
    (hshift : randomBitCount + 1 < 2 ^ (inputLength + 1))
    (herror :
      2 ^ (inputLength + 1) * good ≤ 2 ^ randomBitCount) :
    (randomBitCount + 1) * good < 2 ^ randomBitCount := by
  by_cases hgood : good = 0
  · subst good
    simpa using Nat.pow_pos (n := randomBitCount) (by decide : 0 < (2 : Nat))
  exact
    (Nat.mul_lt_mul_of_pos_right hshift (Nat.pos_of_ne_zero hgood)).trans_le
      herror

theorem natPolynomial_lt_two_pow_eventually (coefficient degree : Nat) :
    ∃ threshold : Nat, ∀ n ≥ threshold,
      coefficient * n ^ degree + 1 < 2 ^ n := by
  have hlimit :
      Filter.Tendsto
        (fun n : Nat => (n : Real) ^ degree / (2 : Real) ^ n)
        Filter.atTop (nhds 0) :=
    tendsto_pow_const_div_const_pow_of_one_lt degree (by norm_num)
  let epsilon : Real := 1 / (coefficient + 1)
  have hepsilon : 0 < epsilon := by
    dsimp [epsilon]
    exact one_div_pos.mpr (by exact_mod_cast Nat.succ_pos coefficient)
  have hratio :
      ∀ᶠ n : Nat in Filter.atTop,
        (n : Real) ^ degree / (2 : Real) ^ n < epsilon :=
    (tendsto_order.1 hlimit).2 epsilon hepsilon
  have hone : ∀ᶠ n : Nat in Filter.atTop, 1 ≤ n :=
    Filter.eventually_ge_atTop 1
  rcases Filter.eventually_atTop.1 (hratio.and hone) with
    ⟨threshold, hthreshold⟩
  refine ⟨threshold, ?_⟩
  intro n hn
  rcases hthreshold n hn with ⟨hratioN, hnOne⟩
  have htwoPow : 0 < (2 : Real) ^ n :=
    pow_pos (by norm_num) _
  have hcoefficient : 0 < (coefficient + 1 : Real) := by
    exact_mod_cast Nat.succ_pos coefficient
  have hratioN' :
      (n : Real) ^ degree <
        epsilon * (2 : Real) ^ n :=
    (div_lt_iff₀ htwoPow).mp hratioN
  have hreal :
      (coefficient + 1 : Real) * (n : Real) ^ degree <
        (2 : Real) ^ n := by
    calc
      (coefficient + 1 : Real) * (n : Real) ^ degree <
          (coefficient + 1 : Real) *
            (epsilon * (2 : Real) ^ n) :=
        mul_lt_mul_of_pos_left hratioN' hcoefficient
      _ = (2 : Real) ^ n := by
        simp [epsilon, hcoefficient.ne']
  have hnat :
      (coefficient + 1) * n ^ degree < 2 ^ n := by
    exact_mod_cast hreal
  have hnpower : 1 ≤ n ^ degree :=
    Nat.one_le_pow degree n (Nat.zero_lt_of_lt hnOne)
  exact
    (calc
      coefficient * n ^ degree + 1 ≤
          coefficient * n ^ degree + n ^ degree :=
        Nat.add_le_add_left hnpower _
      _ = (coefficient + 1) * n ^ degree := by
        simp [Nat.add_mul]).trans_lt hnat

theorem polynomiallyBounded_lt_two_pow_eventually
    {randomBits : Nat → Nat}
    (hrandomBits : PolynomiallyBounded randomBits) :
    ∃ threshold : Nat, ∀ n ≥ threshold,
      randomBits n + 1 < 2 ^ (n + 1) := by
  rcases hrandomBits with ⟨coefficient, degree, hbound⟩
  rcases natPolynomial_lt_two_pow_eventually coefficient degree with
    ⟨threshold, hthreshold⟩
  refine ⟨threshold, ?_⟩
  intro n hn
  have hpoly :
      coefficient * (n + 1) ^ degree + 1 < 2 ^ (n + 1) :=
    hthreshold (n + 1) (hn.trans (Nat.le_succ n))
  exact (Nat.add_le_add_right (hbound n) 1).trans_lt hpoly

theorem PolynomiallyBounded.mono {f g : Nat → Nat}
    (hf : PolynomiallyBounded f) (hgf : ∀ n, g n ≤ f n) :
    PolynomiallyBounded g := by
  rcases hf with ⟨coefficient, degree, hbound⟩
  exact
    ⟨coefficient, degree, fun n => (hgf n).trans (hbound n)⟩

def lautemannExistentialBits (threshold : Nat)
    (randomBits : Nat → Nat) (n : Nat) : Nat :=
  if n < threshold then 0
  else coverExistentialBits (randomBits n)

def lautemannUniversalBits (threshold : Nat)
    (randomBits : Nat → Nat) (n : Nat) : Nat :=
  if n < threshold then 0
  else randomBits n

noncomputable def lautemannVerifier (language : Language)
    (threshold : Nat) (randomBits : Nat → Nat)
    (verifier : List Bool → List Bool → Bool)
    (input existential universal : List Bool) : Bool := by
  classical
  exact if input.length < threshold then
    decide (input ∈ language)
  else
    coverVerifier universal.length verifier
      input existential universal

theorem polynomiallyBounded_lautemannExistentialBits
    (threshold : Nat) {randomBits : Nat → Nat}
    (hrandomBits : PolynomiallyBounded randomBits) :
    PolynomiallyBounded
      (lautemannExistentialBits threshold randomBits) := by
  apply
    (polynomiallyBounded_coverExistentialBits hrandomBits).mono
  intro n
  simp only [lautemannExistentialBits]
  split <;> simp

theorem polynomiallyBounded_lautemannUniversalBits
    (threshold : Nat) {randomBits : Nat → Nat}
    (hrandomBits : PolynomiallyBounded randomBits) :
    PolynomiallyBounded
      (lautemannUniversalBits threshold randomBits) := by
  apply hrandomBits.mono
  intro n
  simp only [lautemannUniversalBits]
  split <;> simp

theorem setCard_acceptingSet
    (verifier : List Bool → List Bool → Bool)
    (input : List Bool) (randomBits : Nat) :
    setCard
        (fun random : BitString randomBits =>
          verifier input random.toList = true) =
      acceptingCard verifier input randomBits := by
  rfl

theorem card_sub_acceptingSet_eq_rejectingCard
    (verifier : List Bool → List Bool → Bool)
    (input : List Bool) (randomBits : Nat) :
    Fintype.card (BitString randomBits) -
        setCard
          (fun random : BitString randomBits =>
            verifier input random.toList = true) =
      rejectingCard verifier input randomBits := by
  rw [setCard_acceptingSet]
  have hsum :=
    acceptingCard_add_rejectingCard verifier input randomBits
  omega

theorem lautemann_characterization
    (language : Language)
    (randomBits : Nat → Nat)
    (verifier : List Bool → List Bool → Bool)
    (herror :
      ∀ input : List Bool,
        (input ∈ language →
          2 ^ (input.length + 1) *
              rejectingCard verifier input (randomBits input.length) ≤
            Fintype.card (BitString (randomBits input.length))) ∧
        (input ∉ language →
          2 ^ (input.length + 1) *
              acceptingCard verifier input (randomBits input.length) ≤
            Fintype.card (BitString (randomBits input.length))))
    (smallCoverObstruction :
      ∀ {n shifts : Nat} (set : BitString n → Prop) [DecidablePred set],
        shifts * setCard set < Fintype.card (BitString n) →
          ∀ translations : Fin shifts → BitString n,
            ¬ shiftedCover set translations)
    (largeCoverExistence :
      ∀ {n shifts : Nat} (set : BitString n → Prop) [DecidablePred set],
        Fintype.card (BitString n) *
              (Fintype.card (BitString n) - setCard set) ^ shifts <
            (Fintype.card (BitString n)) ^ shifts →
          ∃ translations : Fin shifts → BitString n,
            shiftedCover set translations)
    (threshold : Nat)
    (hthreshold : ∀ n ≥ threshold,
      randomBits n + 1 < 2 ^ (n + 1)) :
    ∀ input : List Bool,
      input ∈ language ↔
        ∃ existential :
            BitString
              (lautemannExistentialBits threshold randomBits input.length),
          ∀ universal :
              BitString
                (lautemannUniversalBits threshold randomBits input.length),
            lautemannVerifier language threshold randomBits verifier
                input existential.toList universal.toList = true := by
  classical
  intro input
  by_cases hshort : input.length < threshold
  · simp [lautemannExistentialBits, lautemannUniversalBits,
      lautemannVerifier, hshort]
  rw [show
      lautemannExistentialBits threshold randomBits input.length =
        coverExistentialBits (randomBits input.length) by
      simp [lautemannExistentialBits, hshort]]
  rw [show
      lautemannUniversalBits threshold randomBits input.length =
        randomBits input.length by
      simp [lautemannUniversalBits, hshort]]
  simp only [lautemannVerifier]
  simp only [if_neg hshort]
  let r := randomBits input.length
  let acceptingSet : BitString r → Prop :=
    fun random => verifier input random.toList = true
  constructor
  · intro hmember
    have hreject :=
      (herror input).1 hmember
    have hlarge :
        Fintype.card (BitString r) *
              (Fintype.card (BitString r) -
                setCard acceptingSet) ^ coverShiftCount r <
            (Fintype.card (BitString r)) ^ coverShiftCount r := by
      rw [card_sub_acceptingSet_eq_rejectingCard,
        card_bitString]
      exact largeCoverArithmetic input.length r _
        (by simpa [r, card_bitString] using hreject)
    obtain ⟨translations, hcover⟩ :=
      largeCoverExistence acceptingSet hlarge
    refine ⟨encodeCoverTranslations translations, ?_⟩
    intro point
    have hpointLength : point.toList.length = r := by
      simp [BitString.toList, r]
    rw [hpointLength]
    rw [coverVerifier_encode_iff]
    exact hcover point
  · rintro ⟨encoded, hall⟩
    by_contra hnonmember
    have haccept :=
      (herror input).2 hnonmember
    have hsmall :
        coverShiftCount r * setCard acceptingSet <
          Fintype.card (BitString r) := by
      rw [setCard_acceptingSet, card_bitString]
      exact smallCoverArithmetic input.length r _
        (by
          exact hthreshold input.length (Nat.le_of_not_gt hshort))
        (by simpa [r, card_bitString] using haccept)
    have hnotCover :=
      smallCoverObstruction acceptingSet hsmall
        (unpackCoverTranslations encoded)
    apply hnotCover
    intro point
    have hallPoint := hall point
    have hpointLength : point.toList.length = r := by
      simp [BitString.toList, r]
    rw [hpointLength] at hallPoint
    rw [coverVerifier_toList_iff] at hallPoint
    exact hallPoint

theorem amplified_verifier_implies_sigma_two_of_cover_lemmas_of_dpt
    (language : Language)
    (randomBits : Nat → Nat)
    (verifier : List Bool → List Bool → Bool)
    (hrandomBits : PolynomiallyBounded randomBits)
    (herror :
      ∀ input : List Bool,
        (input ∈ language →
          2 ^ (input.length + 1) *
              rejectingCard verifier input (randomBits input.length) ≤
            Fintype.card (BitString (randomBits input.length))) ∧
        (input ∉ language →
          2 ^ (input.length + 1) *
              acceptingCard verifier input (randomBits input.length) ≤
            Fintype.card (BitString (randomBits input.length))))
    (smallCoverObstruction :
      ∀ {n shifts : Nat} (set : BitString n → Prop) [DecidablePred set],
        shifts * setCard set < Fintype.card (BitString n) →
          ∀ translations : Fin shifts → BitString n,
            ¬ shiftedCover set translations)
    (largeCoverExistence :
      ∀ {n shifts : Nat} (set : BitString n → Prop) [DecidablePred set],
        Fintype.card (BitString n) *
              (Fintype.card (BitString n) - setCard set) ^ shifts <
            (Fintype.card (BitString n)) ^ shifts →
          ∃ translations : Fin shifts → BitString n,
            shiftedCover set translations)
    (threshold : Nat)
    (hthreshold :
      ∀ n ≥ threshold,
        randomBits n + 1 < 2 ^ (n + 1))
    (hlautemannVerifier :
      DecidesInPolynomialTime
        (fun input : Fin 3 → List Bool =>
          lautemannVerifier language threshold randomBits verifier
            (input 0) (input 1) (input 2) = true)) :
    InSigmaTwoP language := by
  refine
    ⟨lautemannExistentialBits threshold randomBits,
      lautemannUniversalBits threshold randomBits,
      lautemannVerifier language threshold randomBits verifier,
      polynomiallyBounded_lautemannExistentialBits
        threshold hrandomBits,
      polynomiallyBounded_lautemannUniversalBits
        threshold hrandomBits,
      hlautemannVerifier, ?_⟩
  exact
    lautemann_characterization
      language randomBits verifier herror
      smallCoverObstruction largeCoverExistence
      threshold hthreshold

theorem lautemannVerifier_dpt_of_coverVerifier_dpt
    (language : Language)
    (threshold : Nat)
    (randomBits : Nat → Nat)
    (verifier : List Bool → List Bool → Bool)
    (hcover :
      DecidesInPolynomialTime
        (fun input : Fin 3 → List Bool =>
          coverVerifier (input 2).length verifier
            (input 0) (input 1) (input 2) = true)) :
    DecidesInPolynomialTime
      (fun input : Fin 3 → List Bool =>
        lautemannVerifier language threshold randomBits verifier
          (input 0) (input 1) (input 2) = true) := by
  classical
  have hoverride :=
    decidesInPolynomialTime_finiteOverride
      (tapes := 2) language threshold
      (fun input : Fin 3 → List Bool =>
        coverVerifier (input 2).length verifier
          (input 0) (input 1) (input 2) = true)
      hcover
  apply hoverride.congr
  intro input
  have hfirst :
      firstTapeIndex 2 = (0 : Fin 3) := by rfl
  rw [hfirst]
  by_cases hshort : (input 0).length < threshold
  · simp [hshort, lautemannVerifier]
  · simp [hshort, lautemannVerifier]

end SipserGacsLautemann
Source
The shifted-cover argument in the Sipser–Gács–Lautemann theorem, including the standard finite-exception cleanup.

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