Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_d015213af699003b208aee4a

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

/-!
# Concrete verifier: malformed serialized circuits
-/

namespace CLRS.Chapter34.Turing.GeneralCircuitVerifier

open Computability StateTransition
open _root_.Turing

private abbrev transition := flip Option.bind step

/-- A non-output gate tag whose gate decoder fails is rejected by the machine. -/
theorem gate_decode_reject (state : State) (symbol : CircuitSym)
    (symbols : List CircuitSym) (inputBits : List Bool) (values : Array Bool)
    (houtput : symbol ≠ .outputMark)
    (hdecode : decodeCircuitGate (symbol :: symbols) = none) :
    Rejects (cfg (some .gates) state (List.map some (symbol :: symbols))
      [] inputBits values.toList.reverse [] values.size 0 0) := by
  cases symbol with
  | inputMark =>
      have hnat : decNat symbols = none := by
        simp [decodeCircuitGate] at hdecode
        exact Option.eq_none_iff_forall_ne_some.mpr (by
          rintro ⟨n, rest⟩ hsome
          exact hdecode n rest hsome)
      have htag := gates_input_step state (List.map some symbols)
        [] inputBits values.toList.reverse [] values.size 0 0
      apply Rejects.before_step (by simpa using htag)
      exact parse_nat_reject_of_decNat_none
        { state with inputBuffer := some (some .inputMark) }
        .inputGate symbols inputBits values.toList.reverse [] values.size 0 0 hnat
  | constFalseMark => simp [decodeCircuitGate] at hdecode
  | constTrueMark => simp [decodeCircuitGate] at hdecode
  | notMark =>
      have hnat : decNat symbols = none := by
        simp [decodeCircuitGate] at hdecode
        exact Option.eq_none_iff_forall_ne_some.mpr (by
          rintro ⟨n, rest⟩ hsome
          exact hdecode n rest hsome)
      have htag := gates_not_step state (List.map some symbols)
        [] inputBits values.toList.reverse [] values.size 0 0
      apply Rejects.before_step (by simpa using htag)
      exact parse_nat_reject_of_decNat_none
        { state with inputBuffer := some (some .notMark) }
        .notGate symbols inputBits values.toList.reverse [] values.size 0 0 hnat
  | andMark =>
      cases hleft : decNat symbols with
      | none =>
          have htag := gates_and_step state (List.map some symbols)
            [] inputBits values.toList.reverse [] values.size 0 0
          apply Rejects.before_step (by simpa using htag)
          exact parse_nat_reject_of_decNat_none
            { state with inputBuffer := some (some .andMark) }
            .andLeft symbols inputBits values.toList.reverse [] values.size 0 0 hleft
      | some decoded =>
          rcases decoded with ⟨left, middle⟩
          have hright : decNat middle = none := by
            simp [decodeCircuitGate, hleft] at hdecode
            exact Option.eq_none_iff_forall_ne_some.mpr (by
              rintro ⟨n, rest⟩ hsome
              exact hdecode n rest hsome)
          have hsymbols := eq_encNat_append_of_decNat_eq_some hleft
          rw [hsymbols]
          have htag := gates_and_step state
            (List.map some (encNat left) ++ List.map some middle)
            [] inputBits values.toList.reverse [] values.size 0 0
          apply Rejects.before_step (by
            simpa [List.map_append, List.append_assoc] using htag)
          rcases parse_nat_phase
              { state with inputBuffer := some (some .andMark) }
              .andLeft left 0 (List.map some middle) [] inputBits
              values.toList.reverse [] values.size 0 with
            ⟨afterLeftParse, hparse⟩
          apply Rejects.before_steps (left + 1)
            (by simpa only [parsedLabel, Nat.zero_add] using hparse)
          by_cases hvalid : left < values.size
          · rcases reverse_split_getD values.toList left hvalid with
              ⟨front, older, hsplit, hlength, holder⟩
            have hcount : front.length + older.length + 1 = values.size := by
              simpa using hlength
            rcases gate_lookup_and_left_phase afterLeftParse front older
                (values.toList.getD left false) (List.map some middle) [] inputBits with
              ⟨afterLookup, hlookup⟩
            change transition^[2 * older.length + 2 * front.length + 6] _ = _ at hlookup
            have hlookup' : transition^[2 * values.size + 4]
                (some (cfg (some (.gateSubtract .andLeft)) afterLeftParse
                  (List.map some middle) [] inputBits values.toList.reverse []
                  values.size left 0)) =
                some (cfg (some (.parseNat
                    (.andRight (values.toList.getD left false))))
                  afterLookup (List.map some middle) [] inputBits
                  values.toList.reverse [] values.size 0 0) := by
              have hcost : 2 * values.size + 4 =
                  2 * older.length + 2 * front.length + 6 := by omega
              rw [hcost, hsplit, ← hcount]
              simpa only [holder] using hlookup
            apply Rejects.before_steps (2 * values.size + 4) hlookup'
            exact parse_nat_reject_of_decNat_none afterLookup
              (.andRight (values.toList.getD left false)) middle inputBits
              values.toList.reverse [] values.size 0 0 hright
          · exact gate_lookup_reject afterLeftParse .andLeft values.size left
              (List.map some middle) inputBits values.toList.reverse [] 0 (by omega)
  | orMark =>
      cases hleft : decNat symbols with
      | none =>
          have htag := gates_or_step state (List.map some symbols)
            [] inputBits values.toList.reverse [] values.size 0 0
          apply Rejects.before_step (by simpa using htag)
          exact parse_nat_reject_of_decNat_none
            { state with inputBuffer := some (some .orMark) }
            .orLeft symbols inputBits values.toList.reverse [] values.size 0 0 hleft
      | some decoded =>
          rcases decoded with ⟨left, middle⟩
          have hright : decNat middle = none := by
            simp [decodeCircuitGate, hleft] at hdecode
            exact Option.eq_none_iff_forall_ne_some.mpr (by
              rintro ⟨n, rest⟩ hsome
              exact hdecode n rest hsome)
          have hsymbols := eq_encNat_append_of_decNat_eq_some hleft
          rw [hsymbols]
          have htag := gates_or_step state
            (List.map some (encNat left) ++ List.map some middle)
            [] inputBits values.toList.reverse [] values.size 0 0
          apply Rejects.before_step (by
            simpa [List.map_append, List.append_assoc] using htag)
          rcases parse_nat_phase
              { state with inputBuffer := some (some .orMark) }
              .orLeft left 0 (List.map some middle) [] inputBits
              values.toList.reverse [] values.size 0 with
            ⟨afterLeftParse, hparse⟩
          apply Rejects.before_steps (left + 1)
            (by simpa only [parsedLabel, Nat.zero_add] using hparse)
          by_cases hvalid : left < values.size
          · rcases reverse_split_getD values.toList left hvalid with
              ⟨front, older, hsplit, hlength, holder⟩
            have hcount : front.length + older.length + 1 = values.size := by
              simpa using hlength
            rcases gate_lookup_or_left_phase afterLeftParse front older
                (values.toList.getD left false) (List.map some middle) [] inputBits with
              ⟨afterLookup, hlookup⟩
            change transition^[2 * older.length + 2 * front.length + 6] _ = _ at hlookup
            have hlookup' : transition^[2 * values.size + 4]
                (some (cfg (some (.gateSubtract .orLeft)) afterLeftParse
                  (List.map some middle) [] inputBits values.toList.reverse []
                  values.size left 0)) =
                some (cfg (some (.parseNat
                    (.orRight (values.toList.getD left false))))
                  afterLookup (List.map some middle) [] inputBits
                  values.toList.reverse [] values.size 0 0) := by
              have hcost : 2 * values.size + 4 =
                  2 * older.length + 2 * front.length + 6 := by omega
              rw [hcost, hsplit, ← hcount]
              simpa only [holder] using hlookup
            apply Rejects.before_steps (2 * values.size + 4) hlookup'
            exact parse_nat_reject_of_decNat_none afterLookup
              (.orRight (values.toList.getD left false)) middle inputBits
              values.toList.reverse [] values.size 0 0 hright
          · exact gate_lookup_reject afterLeftParse .orLeft values.size left
              (List.map some middle) inputBits values.toList.reverse [] 0 (by omega)
  | outputMark => exact False.elim (houtput rfl)
  | argMark =>
      exact rejects_after_cleanup_step _ _ (List.map some symbols) inputBits
        values.toList.reverse [] values.size 0 0
        (gates_bad_marker_reject_step state .argMark (Or.inl rfl)
          (List.map some symbols) [] inputBits values.toList.reverse [] values.size 0 0)
  | endMark =>
      exact rejects_after_cleanup_step _ _ (List.map some symbols) inputBits
        values.toList.reverse [] values.size 0 0
        (gates_bad_marker_reject_step state .endMark (Or.inr rfl)
          (List.map some symbols) [] inputBits values.toList.reverse [] values.size 0 0)

/-- A gate stream whose structural decoder fails is rejected.  The fuel
hypothesis is the one used by `decodeCircuit`: at least the remaining symbol
count, so failure cannot be an artificial fuel exhaustion. -/
theorem gate_stream_reject_of_decode_none (state : State) (fuel : Nat)
    (symbols : List CircuitSym) (inputBits : List Bool) (values : Array Bool)
    (hfuel : symbols.length ≤ fuel)
    (hdecode : decodeCircuitGates fuel symbols = none) :
    Rejects (cfg (some .gates) state (List.map some symbols)
      [] inputBits values.toList.reverse [] values.size 0 0) := by
  induction fuel generalizing state symbols values with
  | zero =>
      have hempty : symbols = [] := by
        cases symbols <;> simp_all
      subst symbols
      exact rejects_after_cleanup_step _ _ [] inputBits values.toList.reverse []
        values.size 0 0
        (gates_eof_reject_step state [] inputBits values.toList.reverse []
          values.size 0 0)
  | succ fuel ih =>
      cases symbols with
      | nil =>
          exact rejects_after_cleanup_step _ _ [] inputBits values.toList.reverse []
            values.size 0 0
            (gates_eof_reject_step state [] inputBits values.toList.reverse []
              values.size 0 0)
      | cons symbol symbols =>
          by_cases hout : symbol = .outputMark
          · subst symbol
            have hnat : decNat symbols = none := by
              simp [decodeCircuitGates] at hdecode
              exact Option.eq_none_iff_forall_ne_some.mpr (by
                rintro ⟨n, rest⟩ hsome
                exact hdecode n rest hsome)
            have htag := gates_output_step state (List.map some symbols)
              [] inputBits values.toList.reverse [] values.size 0 0
            apply Rejects.before_step (by simpa using htag)
            exact parse_nat_reject_of_decNat_none
              { state with inputBuffer := some (some .outputMark) }
              .outputGate symbols inputBits values.toList.reverse []
              values.size 0 0 hnat
          · cases hgate : decodeCircuitGate (symbol :: symbols) with
            | none =>
                exact gate_decode_reject state symbol symbols inputBits values
                  hout hgate
            | some decoded =>
                rcases decoded with ⟨gate, rest⟩
                have hrestDecode : decodeCircuitGates fuel rest = none := by
                  cases symbol <;> simp_all [decodeCircuitGates]
                  all_goals
                    exact Option.eq_none_iff_forall_ne_some.mpr (by
                      rintro ⟨gates, output, trailing⟩ hsome
                      exact hdecode gates output trailing hsome)
                have hsymbols :=
                  eq_encodeCircuitGate_append_of_decodeCircuitGate_eq_some hgate
                have hgateLength : 1 ≤ (encodeCircuitGate gate).length := by
                  cases gate with
                  | input i => simp [encodeCircuitGate]
                  | const value => cases value <;> simp [encodeCircuitGate]
                  | not source => simp [encodeCircuitGate]
                  | and left right => simp [encodeCircuitGate]
                  | or left right => simp [encodeCircuitGate]
                have hrestFuel : rest.length ≤ fuel := by
                  have hlength := congrArg List.length hsymbols
                  simp only [List.length_cons, List.length_append] at hlength hfuel
                  omega
                rw [hsymbols]
                by_cases hvalid : gate.ValidAt inputBits.length values.size
                · let nextValues := values.push
                    (gate.evalWith (fun i => inputBits.getD i false) values)
                  rcases gate_phase state gate inputBits values (List.map some rest)
                      hvalid with ⟨afterGate, hrun⟩
                  apply Rejects.before_steps (gateSteps values.size gate)
                  · simpa [List.map_append] using hrun
                  · simpa [nextValues, List.getD_eq_getElem?_getD,
                      Array.toList_push, List.reverse_append] using
                      ih afterGate rest nextValues hrestFuel hrestDecode
                · simpa [List.map_append] using
                    gate_reject_of_not_valid state gate inputBits values
                      (List.map some rest) hvalid

/-- A structurally decoded gate stream with unconsumed trailing symbols is
rejected at the output boundary (or earlier at its first invalid gate). -/
theorem gate_stream_reject_of_trailing (state : State) (fuel : Nat)
    (symbols : List CircuitSym) (inputBits : List Bool) (values : Array Bool)
    (gates : List CircuitGate) (outputIndex : Nat) (trailing : List CircuitSym)
    (hdecode : decodeCircuitGates fuel symbols =
      some (gates, outputIndex, trailing))
    (htrailing : trailing ≠ []) :
    Rejects (cfg (some .gates) state (List.map some symbols)
      [] inputBits values.toList.reverse [] values.size 0 0) := by
  have hsymbols :=
    eq_encodeCircuitGates_append_of_decodeCircuitGates_eq_some hdecode
  rw [hsymbols]
  let outputInput :=
    List.map some (.outputMark :: encNat outputIndex ++ trailing)
  have hinputMap :
      List.map some
          (gates.flatMap encodeCircuitGate ++
            .outputMark :: encNat outputIndex ++ trailing) =
        List.map some (gates.flatMap encodeCircuitGate) ++ outputInput := by
    simp [outputInput, List.map_append, List.append_assoc]
  rw [hinputMap]
  by_cases hgates : ∀ i (hi : i < gates.length),
      (gates.get ⟨i, hi⟩).ValidAt inputBits.length (values.size + i)
  · rcases gate_list_phase state gates inputBits values outputInput hgates with
      ⟨afterGates, hrun⟩
    let finalValues := evalGateList inputBits values gates
    have hrun' : transition^[gateListSteps values.size gates]
        (some (cfg (some .gates) state
          (List.map some (gates.flatMap encodeCircuitGate) ++ outputInput)
          [] inputBits values.toList.reverse [] values.size 0 0)) =
        some (cfg (some .gates) afterGates outputInput [] inputBits
          finalValues.toList.reverse [] finalValues.size 0 0) := by
      simpa [finalValues] using hrun
    apply Rejects.before_steps (gateListSteps values.size gates)
    · exact hrun'
    · have htag := gates_output_step afterGates
          (List.map some (encNat outputIndex ++ trailing)) [] inputBits
          finalValues.toList.reverse [] finalValues.size 0 0
      apply Rejects.before_step (by
        simpa only [outputInput, List.map_cons, List.map_append,
          List.cons_append] using htag)
      rcases parse_nat_phase
          { afterGates with inputBuffer := some (some .outputMark) }
          .outputGate outputIndex 0 (List.map some trailing) [] inputBits
          finalValues.toList.reverse [] finalValues.size 0 with
        ⟨afterParse, hparse⟩
      have hparse' : transition^[outputIndex + 1]
          (some (cfg (some (.parseNat .outputGate))
            { afterGates with inputBuffer := some (some .outputMark) }
            (List.map some (encNat outputIndex) ++ List.map some trailing)
            [] inputBits finalValues.toList.reverse [] finalValues.size 0 0)) =
          some (cfg (some .checkTrailing) afterParse (List.map some trailing)
            [] inputBits finalValues.toList.reverse [] finalValues.size outputIndex 0) := by
        simpa only [parsedLabel, Nat.zero_add] using hparse
      apply Rejects.before_steps (outputIndex + 1) hparse'
      cases trailing with
      | nil => contradiction
      | cons head tail =>
          exact rejects_after_cleanup_step _ _ (List.map some tail) inputBits
            finalValues.toList.reverse [] finalValues.size outputIndex 0
            (by
              simpa using check_trailing_nonempty_step afterParse (some head)
                (List.map some tail) [] inputBits finalValues.toList.reverse []
                finalValues.size outputIndex 0)
  · exact gate_list_reject_of_not_valid state gates inputBits values outputInput hgates

/-- Every input rejected by the public circuit decoder reaches `[false]`. -/
theorem malformed_circuit_reject (certificate input : List CircuitSym)
    (hdecode : decodeCircuit input = none) :
    Rejects (initList machine (pairEncoding certificate input)) := by
  rcases certificate_header_phase certificate input with
    ⟨afterHeader, hheaderValid, hheaderRun⟩
  apply Rejects.before_steps (2 * (certificate.length + 1)) hheaderRun
  cases hnat : decNat input with
  | none =>
      exact input_count_reject_of_decNat_none afterHeader input
        (assignmentBits certificate) [] [] certificate.length 0 0 hnat
  | some decodedNat =>
      rcases decodedNat with ⟨inputCount, rest⟩
      have hinput := eq_encNat_append_of_decNat_eq_some hnat
      rw [hinput]
      by_cases hlength : certificate.length = inputCount
      · by_cases hlegal : certificate.all isAssignmentSymbol = true
        · have hstateValid : afterHeader.validAssignment = true := by
            rw [hheaderValid, hlegal]
          rcases input_count_phase afterHeader inputCount (List.map some rest)
              (assignmentBits certificate) [] [] 0 0 hstateValid with
            ⟨afterCount, hcount⟩
          apply Rejects.before_steps (inputCount + 1) (by
            simpa [List.map_append, hlength] using hcount)
          cases hgates : decodeCircuitGates rest.length rest with
          | none =>
              exact gate_stream_reject_of_decode_none afterCount rest.length rest
                (assignmentBits certificate) #[] (by omega) hgates
          | some decodedGates =>
              rcases decodedGates with ⟨gates, outputIndex, trailing⟩
              have htrailing : trailing ≠ [] := by
                intro hempty
                subst trailing
                simp [decodeCircuit, hnat, hgates] at hdecode
              exact gate_stream_reject_of_trailing afterCount rest.length rest
                (assignmentBits certificate) #[] gates outputIndex trailing
                hgates htrailing
        · have hfalse : certificate.all isAssignmentSymbol = false := by
            cases hvalue : certificate.all isAssignmentSymbol <;> simp_all
          simpa [List.map_append] using
            input_count_reject afterHeader inputCount certificate.length
              (List.map some rest) (assignmentBits certificate) [] [] 0 0
              (Or.inr (by rw [hheaderValid]; exact hfalse))
      · simpa [List.map_append] using
          input_count_reject afterHeader inputCount certificate.length
            (List.map some rest) (assignmentBits certificate) [] [] 0 0
            (Or.inl hlength)

/-- The concrete machine computes the correct Boolean on every malformed
circuit input. -/
theorem malformed_run (certificate input : List CircuitSym)
    (hdecode : decodeCircuit input = none) :
    ∃ steps,
      transition^[steps]
        (some (initList machine (pairEncoding certificate input))) =
        some (haltList machine [generalCircuitVerifier certificate input]) := by
  rcases malformed_circuit_reject certificate input hdecode with ⟨steps, hrun⟩
  exact ⟨steps, by simpa [generalCircuitVerifier, hdecode] using hrun⟩

/-- Unbounded exact correctness of the concrete machine on every pair.  The
separate runtime layer upgrades this result to polynomial time. -/
theorem verifier_run (certificate input : List CircuitSym) :
    ∃ steps,
      transition^[steps]
        (some (initList machine (pairEncoding certificate input))) =
        some (haltList machine [generalCircuitVerifier certificate input]) := by
  cases hdecode : decodeCircuit input with
  | none => exact malformed_run certificate input hdecode
  | some c =>
      have hcanonical := encodeCircuit_of_decodeCircuit_eq_some hdecode
      subst input
      exact canonical_run certificate c

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