Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_3d52b2d1b9bbe8af79a134df

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_dc530da3af266ce325fbfb37
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Concrete verifier: rejecting one-step contracts
-/

namespace CLRS.Chapter34.Turing.GeneralCircuitVerifier

attribute [local simp] setInput setBool setCounter inputIs hasInput hasBool
  hasCounter bufferedBool hasEncodedSymbol bufferedAssignmentValue
  noteAssignmentSymbol go reject finishGate finishLookup popBool pushBool
  moveBufferedBool


theorem scan_eof_reject_step (state : State)
    (output certificate values scratch : List Bool)
    (gateCount index saved : Nat) :
    step (cfg (some .scanCertificate) state [] output certificate values scratch
      gateCount index saved) =
      some (cfg (some (.clearInput false))
        { state with inputBuffer := none }
        [] output certificate values scratch gateCount index saved) := by
  exact (by
    apply congrArg some
    apply _root_.Turing.TM2Comp.Cfg_ext
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · funext stack
      cases stack <;>
        simp [step, cfg, machine, program, stackContents, List.replicate_succ,
          Function.update]
)

theorem input_count_arg_underflow_step (state : State)
    (input : List (Option CircuitSym))
    (output certificate values scratch : List Bool) (index saved : Nat) :
    step (cfg (some .inputCount) state (some .argMark :: input)
      output certificate values scratch 0 index saved) =
      some (cfg (some (.clearInput false))
        { state with inputBuffer := some (some .argMark), counterPresent := false }
        input output certificate values scratch 0 index saved) := by
  exact (by
    apply congrArg some
    apply _root_.Turing.TM2Comp.Cfg_ext
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · funext stack
      cases stack <;>
        simp [step, cfg, machine, program, stackContents, List.replicate_succ,
          Function.update]
)

theorem input_count_end_nonempty_step (state : State)
    (input : List (Option CircuitSym))
    (output certificate values scratch : List Bool)
    (gateCount index saved : Nat) :
    step (cfg (some .inputCount) state (some .endMark :: input)
      output certificate values scratch (gateCount + 1) index saved) =
      some (cfg (some (.clearInput false))
        { state with inputBuffer := some (some .endMark), counterPresent := true }
        input output certificate values scratch gateCount index saved) := by
  exact (by
    apply congrArg some
    apply _root_.Turing.TM2Comp.Cfg_ext
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · funext stack
      cases stack <;>
        simp [step, cfg, machine, program, stackContents, List.replicate_succ,
          Function.update]
)

theorem input_count_end_invalid_step (state : State)
    (input : List (Option CircuitSym))
    (output certificate values scratch : List Bool) (index saved : Nat)
    (hinvalid : state.validAssignment = false) :
    step (cfg (some .inputCount) state (some .endMark :: input)
      output certificate values scratch 0 index saved) =
      some (cfg (some (.clearInput false))
        { state with inputBuffer := some (some .endMark), counterPresent := false }
        input output certificate values scratch 0 index saved) := by
  rcases state with ⟨inputBuffer, boolBuffer, counterPresent, validAssignment⟩
  simp only [State.validAssignment] at hinvalid
  subst validAssignment
  exact (by
    apply congrArg some
    apply _root_.Turing.TM2Comp.Cfg_ext
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · funext stack
      cases stack <;>
        simp [step, cfg, machine, program, stackContents, List.replicate_succ,
          Function.update]
)

theorem input_count_eof_reject_step (state : State)
    (output certificate values scratch : List Bool)
    (gateCount index saved : Nat) :
    step (cfg (some .inputCount) state [] output certificate values scratch
      gateCount index saved) =
      some (cfg (some (.clearInput false)) { state with inputBuffer := none }
        [] output certificate values scratch gateCount index saved) := by
  exact (by
    apply congrArg some
    apply _root_.Turing.TM2Comp.Cfg_ext
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · funext stack
      cases stack <;>
        simp [step, cfg, machine, program, stackContents, List.replicate_succ,
          Function.update]
)

theorem input_count_bad_symbol_reject_step (state : State) (symbol : CircuitSym)
    (harg : symbol ≠ .argMark) (hend : symbol ≠ .endMark)
    (input : List (Option CircuitSym))
    (output certificate values scratch : List Bool)
    (gateCount index saved : Nat) :
    step (cfg (some .inputCount) state (some symbol :: input)
      output certificate values scratch gateCount index saved) =
      some (cfg (some (.clearInput false))
        { state with inputBuffer := some (some symbol) }
        input output certificate values scratch gateCount index saved) := by
  cases symbol <;> simp_all <;> exact (by
    apply congrArg some
    apply _root_.Turing.TM2Comp.Cfg_ext
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · funext stack
      cases stack <;>
        simp [step, cfg, machine, program, stackContents, List.replicate_succ,
          Function.update]
)

theorem parse_nat_eof_reject_step (state : State) (ret : Return)
    (output certificate values scratch : List Bool)
    (gateCount index saved : Nat) :
    step (cfg (some (.parseNat ret)) state [] output certificate values scratch
      gateCount index saved) =
      some (cfg (some (.clearInput false)) { state with inputBuffer := none }
        [] output certificate values scratch gateCount index saved) := by
  cases ret <;> exact (by
    apply congrArg some
    apply _root_.Turing.TM2Comp.Cfg_ext
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · funext stack
      cases stack <;>
        simp [step, cfg, machine, program, stackContents, List.replicate_succ,
          Function.update]
)

theorem parse_nat_bad_symbol_reject_step (state : State) (ret : Return)
    (symbol : CircuitSym) (harg : symbol ≠ .argMark) (hend : symbol ≠ .endMark)
    (input : List (Option CircuitSym))
    (output certificate values scratch : List Bool)
    (gateCount index saved : Nat) :
    step (cfg (some (.parseNat ret)) state (some symbol :: input)
      output certificate values scratch gateCount index saved) =
      some (cfg (some (.clearInput false))
        { state with inputBuffer := some (some symbol) }
        input output certificate values scratch gateCount index saved) := by
  cases ret <;> cases symbol <;> simp_all <;> exact (by
    apply congrArg some
    apply _root_.Turing.TM2Comp.Cfg_ext
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · funext stack
      cases stack <;>
        simp [step, cfg, machine, program, stackContents, List.replicate_succ,
          Function.update]
)

theorem gates_eof_reject_step (state : State)
    (output certificate values scratch : List Bool)
    (gateCount index saved : Nat) :
    step (cfg (some .gates) state [] output certificate values scratch
      gateCount index saved) =
      some (cfg (some (.clearInput false)) { state with inputBuffer := none }
        [] output certificate values scratch gateCount index saved) := by
  exact (by
    apply congrArg some
    apply _root_.Turing.TM2Comp.Cfg_ext
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · funext stack
      cases stack <;>
        simp [step, cfg, machine, program, stackContents, List.replicate_succ,
          Function.update]
)

theorem gates_bad_marker_reject_step (state : State) (symbol : CircuitSym)
    (harg : symbol = .argMark ∨ symbol = .endMark)
    (input : List (Option CircuitSym))
    (output certificate values scratch : List Bool)
    (gateCount index saved : Nat) :
    step (cfg (some .gates) state (some symbol :: input)
      output certificate values scratch gateCount index saved) =
      some (cfg (some (.clearInput false))
        { state with inputBuffer := some (some symbol) }
        input output certificate values scratch gateCount index saved) := by
  rcases harg with rfl | rfl <;> exact (by
    apply congrArg some
    apply _root_.Turing.TM2Comp.Cfg_ext
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · funext stack
      cases stack <;>
        simp [step, cfg, machine, program, stackContents, List.replicate_succ,
          Function.update]
)

theorem certificate_lookup_prefix_underflow_step (state : State)
    (input : List (Option CircuitSym)) (output values scratch : List Bool)
    (gateCount index saved : Nat) :
    step (cfg (some .certificateLookup) state input output [] values scratch
      gateCount (index + 1) saved) =
      some (cfg (some (.clearInput false))
        { state with boolBuffer := none, counterPresent := true }
        input output [] values scratch gateCount index saved) := by
  exact (by
    apply congrArg some
    apply _root_.Turing.TM2Comp.Cfg_ext
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · funext stack
      cases stack <;>
        simp [step, cfg, machine, program, stackContents, List.replicate_succ,
          Function.update]
)

theorem certificate_lookup_target_underflow_step (state : State)
    (input : List (Option CircuitSym)) (output values scratch : List Bool)
    (gateCount saved : Nat) :
    step (cfg (some .certificateLookup) state input output [] values scratch
      gateCount 0 saved) =
      some (cfg (some (.clearInput false))
        { state with boolBuffer := none, counterPresent := false }
        input output [] values scratch gateCount 0 saved) := by
  exact (by
    apply congrArg some
    apply _root_.Turing.TM2Comp.Cfg_ext
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · funext stack
      cases stack <;>
        simp [step, cfg, machine, program, stackContents, List.replicate_succ,
          Function.update]
)

theorem gate_subtract_underflow_step (state : State) (ret : Return)
    (input : List (Option CircuitSym))
    (output certificate values scratch : List Bool)
    (index saved : Nat) :
    step (cfg (some (.gateSubtract ret)) state input output certificate values scratch
      0 (index + 1) saved) =
      some (cfg (some (.clearInput false))
        { state with counterPresent := false }
        input output certificate values scratch 0 index saved) := by
  cases ret <;> exact (by
    apply congrArg some
    apply _root_.Turing.TM2Comp.Cfg_ext
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · funext stack
      cases stack <;>
        simp [step, cfg, machine, program, stackContents, List.replicate_succ,
          Function.update]
)

theorem gate_transfer_first_underflow_step (state : State) (ret : Return)
    (input : List (Option CircuitSym))
    (output certificate values scratch : List Bool) (saved : Nat) :
    step (cfg (some (.gateTransferFirst ret)) state input output certificate values scratch
      0 0 saved) =
      some (cfg (some (.clearInput false))
        { state with counterPresent := false }
        input output certificate values scratch 0 0 saved) := by
  cases ret <;> exact (by
    apply congrArg some
    apply _root_.Turing.TM2Comp.Cfg_ext
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · funext stack
      cases stack <;>
        simp [step, cfg, machine, program, stackContents, List.replicate_succ,
          Function.update]
)

theorem check_trailing_nonempty_step (state : State)
    (head : Option CircuitSym) (input : List (Option CircuitSym))
    (output certificate values scratch : List Bool)
    (gateCount index saved : Nat) :
    step (cfg (some .checkTrailing) state (head :: input)
      output certificate values scratch gateCount index saved) =
      some (cfg (some (.clearInput false))
        { state with inputBuffer := some head }
        input output certificate values scratch gateCount index saved) := by
  cases head with
  | none => exact (by
    apply congrArg some
    apply _root_.Turing.TM2Comp.Cfg_ext
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · funext stack
      cases stack <;>
        simp [step, cfg, machine, program, stackContents, List.replicate_succ,
          Function.update]
)
  | some sym => cases sym <;> exact (by
    apply congrArg some
    apply _root_.Turing.TM2Comp.Cfg_ext
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · simp [step, cfg, machine, program, stackContents, List.replicate_succ,
        Function.update]
    · funext stack
      cases stack <;>
        simp [step, cfg, machine, program, stackContents, List.replicate_succ,
          Function.update]
)

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