Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Correctness of one encoded verifier call

Definition
sgl_verifier_call_correctness

by Henry Yuen · Jul 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorypolynomial-timeturing-machines

This module specializes the encoded-simulator padded-time correctness theorem to the verifier predicate used in the Sipser--Gács--Lautemann scheduler. Given a concrete two-tape verifier machine for V(x,r)V(x,r)V(x,r), if the encoded simulator is run on encoded query tapes for any time at least six times the verifier time bound, then accepting is equivalent to V(x,r)=trueV(x,r)=\mathrm{true}V(x,r)=true and rejecting is equivalent to its negation.

This isolates the final readout step for each scheduled verifier call. The remaining scheduler construction still has to build the encoded query tapes and aggregate many such calls.

Definition code
import Definitions.Def_sgl_encoded_padded_correctness

namespace SipserGacsLautemann

theorem encodedVerifierCall_correctness_at_larger_time
    (verifier : List Bool → List Bool → Bool)
    {states : Nat}
    (machine : Machine 2 states)
    (time : Nat → Nat)
    (hcorrect :
      ∀ input : Fin 2 → List Bool,
        (machine.acceptsWithin input
            (time (totalInputLength input)) ↔
          verifier (input 0) (input 1) = true) ∧
        (machine.rejectsWithin input
            (time (totalInputLength input)) ↔
          ¬ verifier (input 0) (input 1) = true))
    (query : Fin 2 → List Bool)
    {later : Nat}
    (hle : 6 * time (totalInputLength query) ≤ later) :
    (((encodedSimulationTypedMachine machine).toMachine
          ).acceptsWithin
        (fun i => encodeInputBits (query i)) later ↔
        verifier (query 0) (query 1) = true) ∧
      (((encodedSimulationTypedMachine machine).toMachine
          ).rejectsWithin
        (fun i => encodeInputBits (query i)) later ↔
        ¬ verifier (query 0) (query 1) = true) := by
  exact
    encodedSimulation_toMachine_correctness_at_larger_time
      machine
      (fun input : Fin 2 → List Bool =>
        verifier (input 0) (input 1) = true)
      query hle (hcorrect query).1 (hcorrect query).2

theorem encodedVerifierCall_accepts_iff
    (verifier : List Bool → List Bool → Bool)
    {states : Nat}
    (machine : Machine 2 states)
    (time : Nat → Nat)
    (hcorrect :
      ∀ input : Fin 2 → List Bool,
        (machine.acceptsWithin input
            (time (totalInputLength input)) ↔
          verifier (input 0) (input 1) = true) ∧
        (machine.rejectsWithin input
            (time (totalInputLength input)) ↔
          ¬ verifier (input 0) (input 1) = true))
    (input random : List Bool)
    {later : Nat}
    (hle :
      6 * time
          (totalInputLength
            (fun i : Fin 2 =>
              if i = 0 then input else random)) ≤ later) :
    (((encodedSimulationTypedMachine machine).toMachine
          ).acceptsWithin
        (fun i : Fin 2 =>
          encodeInputBits
            (if i = 0 then input else random)) later ↔
        verifier input random = true) := by
  let query : Fin 2 → List Bool :=
    fun i => if i = 0 then input else random
  have hcall :=
    encodedVerifierCall_correctness_at_larger_time
      verifier machine time hcorrect query hle
  simpa [query] using hcall.1

theorem encodedVerifierCall_rejects_iff
    (verifier : List Bool → List Bool → Bool)
    {states : Nat}
    (machine : Machine 2 states)
    (time : Nat → Nat)
    (hcorrect :
      ∀ input : Fin 2 → List Bool,
        (machine.acceptsWithin input
            (time (totalInputLength input)) ↔
          verifier (input 0) (input 1) = true) ∧
        (machine.rejectsWithin input
            (time (totalInputLength input)) ↔
          ¬ verifier (input 0) (input 1) = true))
    (input random : List Bool)
    {later : Nat}
    (hle :
      6 * time
          (totalInputLength
            (fun i : Fin 2 =>
              if i = 0 then input else random)) ≤ later) :
    (((encodedSimulationTypedMachine machine).toMachine
          ).rejectsWithin
        (fun i : Fin 2 =>
          encodeInputBits
            (if i = 0 then input else random)) later ↔
        ¬ verifier input random = true) := by
  let query : Fin 2 → List Bool :=
    fun i => if i = 0 then input else random
  have hcall :=
    encodedVerifierCall_correctness_at_larger_time
      verifier machine time hcorrect query hle
  simpa [query] using hcall.2

end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission; specialization of the published encoded simulator and padded-time correctness lemmas to verifier calls.

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