Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.GeneralCircuit.VerifierMachine.CanonicalRun

Definition
PricingWithTips3DM_5f8cde248eba0e74c4ec3c2c

by qmaai2907271020 · Oct 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorypricing-with-tipsthree-dimensional-matching

A private, kernel-checked dependency module used by the formal NP-hardness proof for three-dimensional matching and Theorems 4.1 and 4.2 of arXiv:2507.10872.

Definition code
import Definitions.Def_PricingWithTips3DM_3b185be820be8b52572791f6
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Concrete verifier: complete behavior on canonical circuit encodings
-/

namespace CLRS.Chapter34.Turing.GeneralCircuitVerifier

open Computability StateTransition
open _root_.Turing

private abbrev transition := flip Option.bind step

/-- Scan and restore an arbitrary certificate before starting the circuit
header check. -/
theorem certificate_header_phase (certificate : List CircuitSym)
    (circuitInput : List CircuitSym) :
    ∃ finalState,
      finalState.validAssignment = certificate.all isAssignmentSymbol ∧
      transition^[2 * (certificate.length + 1)]
        (some (initList machine (pairEncoding certificate circuitInput))) =
        some (cfg (some .inputCount) finalState (List.map some circuitInput)
          [] (assignmentBits certificate) [] [] certificate.length 0 0) := by
  rcases scan_phase initialState certificate (List.map some circuitInput)
      [] [] [] [] 0 0 0 with ⟨afterScan, hscanValid, hscan⟩
  rcases reverse_phase afterScan (assignmentBits certificate).reverse
      (List.map some circuitInput) [] [] [] certificate.length 0 0 with
    ⟨afterReverse, hreverseValid, hreverse⟩
  have hscan' : transition^[certificate.length + 1]
      (some (initList machine (pairEncoding certificate circuitInput))) =
      some (cfg (some .reverseCertificate) afterScan
        (List.map some circuitInput) [] [] []
        (assignmentBits certificate).reverse certificate.length 0 0) := by
    rw [initList_eq_cfg]
    simpa [pairEncoding, assignmentBits, List.append_assoc] using hscan
  have hreverse' : transition^[certificate.length + 1]
      (some (cfg (some .reverseCertificate) afterScan
        (List.map some circuitInput) [] [] []
        (assignmentBits certificate).reverse certificate.length 0 0)) =
      some (cfg (some .inputCount) afterReverse (List.map some circuitInput)
        [] (assignmentBits certificate) [] [] certificate.length 0 0) := by
    simpa using hreverse
  refine ⟨afterReverse, ?_, ?_⟩
  · rw [hreverseValid, hscanValid]
    simp [initialState]
  · have hfull := step_comp (certificate.length + 1)
      (certificate.length + 1) hscan' hreverse'
    have hsteps : 2 * (certificate.length + 1) =
        (certificate.length + 1) + (certificate.length + 1) := by omega
    rw [hsteps]
    exact hfull

/-- Every canonical circuit whose static checks fail reaches `[false]`. -/
theorem canonical_reject (certificate : List CircuitSym) (c : Circuit)
    (hbad : ¬ c.WellFormed ∨
      certificate.length ≠ c.inputCount ∨
      certificate.all isAssignmentSymbol = false) :
    Rejects (initList machine (pairEncoding certificate (encodeCircuit c))) := by
  rcases certificate_header_phase certificate (encodeCircuit c) with
    ⟨afterHeader, hheaderValid, hheader⟩
  apply Rejects.before_steps (2 * (certificate.length + 1)) hheader
  let gateInput :=
    List.map some (c.gates.flatMap encodeCircuitGate) ++
      List.map some (.outputMark :: encNat c.output)
  have hencoded : List.map some (encodeCircuit c) =
      List.map some (encNat c.inputCount) ++ gateInput := by
    simp [encodeCircuit, gateInput, List.map_append, List.append_assoc]
  rw [hencoded]
  by_cases hlength : certificate.length = c.inputCount
  · by_cases hlegal : certificate.all isAssignmentSymbol = true
    · have hstateValid : afterHeader.validAssignment = true := by
        rw [hheaderValid, hlegal]
      rcases input_count_phase afterHeader c.inputCount gateInput
          (assignmentBits certificate) [] [] 0 0 hstateValid with
        ⟨afterCount, hcount⟩
      apply Rejects.before_steps (c.inputCount + 1) (by
        simpa [hlength] using hcount)
      have hnwf : ¬ c.WellFormed := by
        rcases hbad with hnwf | hrest
        · exact hnwf
        · rcases hrest with hne | hfalse
          · exact False.elim (hne hlength)
          · rw [hlegal] at hfalse
            contradiction
      exact circuit_body_reject_of_not_wellFormed afterCount c
        (assignmentBits certificate) (by simp [hlength]) hnwf
    · have hfalse : certificate.all isAssignmentSymbol = false := by
        cases hvalue : certificate.all isAssignmentSymbol <;> simp_all
      exact input_count_reject afterHeader c.inputCount certificate.length gateInput
        (assignmentBits certificate) [] [] 0 0
        (Or.inr (by rw [hheaderValid]; exact hfalse))
  · exact input_count_reject afterHeader c.inputCount certificate.length gateInput
      (assignmentBits certificate) [] [] 0 0 (Or.inl hlength)

/-- Complete exact result for every legal certificate of the declared length
and every canonical well-formed circuit, including a false evaluation. -/
theorem canonical_wellFormed_run (certificate : List CircuitSym) (c : Circuit)
    (hwf : c.WellFormed)
    (hlength : certificate.length = c.inputCount)
    (hlegal : certificate.all isAssignmentSymbol = true) :
    ∃ steps,
      transition^[steps]
        (some (initList machine (pairEncoding certificate (encodeCircuit c)))) =
        some (haltList machine [generalCircuitVerifier certificate (encodeCircuit c)]) := by
  refine ⟨successfulSteps certificate c, ?_⟩
  simpa [generalCircuitVerifier, decodeCircuit_encodeCircuit, hwf, hlength, hlegal]
    using successful_run certificate c hwf hlength hlegal

/-- Complete result for every certificate and canonical circuit encoding. -/
theorem canonical_run (certificate : List CircuitSym) (c : Circuit) :
    ∃ steps,
      transition^[steps]
        (some (initList machine (pairEncoding certificate (encodeCircuit c)))) =
        some (haltList machine [generalCircuitVerifier certificate (encodeCircuit c)]) := by
  by_cases hwf : c.WellFormed
  · by_cases hlength : certificate.length = c.inputCount
    · by_cases hlegal : certificate.all isAssignmentSymbol = true
      · exact canonical_wellFormed_run certificate c hwf hlength hlegal
      · have hfalse : certificate.all isAssignmentSymbol = false := by
          cases hvalue : certificate.all isAssignmentSymbol <;> simp_all
        rcases canonical_reject certificate c (Or.inr (Or.inr hfalse)) with
          ⟨steps, hrun⟩
        refine ⟨steps, ?_⟩
        simpa [generalCircuitVerifier, decodeCircuit_encodeCircuit, hwf, hlength,
          hfalse] using hrun
    · rcases canonical_reject certificate c (Or.inr (Or.inl hlength)) with
        ⟨steps, hrun⟩
      refine ⟨steps, ?_⟩
      simpa [generalCircuitVerifier, decodeCircuit_encodeCircuit, hwf, hlength]
        using hrun
  · rcases canonical_reject certificate c (Or.inl hwf) with ⟨steps, hrun⟩
    refine ⟨steps, ?_⟩
    simpa [generalCircuitVerifier, decodeCircuit_encodeCircuit, hwf] using hrun

end CLRS.Chapter34.Turing.GeneralCircuitVerifier
Source
https://github.com/tanktechnology/CLRS-Lean

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