Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.GeneralCircuit.ToSAT.Machine.Emitter.Header

Definition
PricingWithTips3DM_35ca25960ddfb56d04b4daa1

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

/-! # General-circuit formula emitter: canonical record header -/

namespace CLRS.Chapter34.Turing.GeneralCircuitToSAT.Emitter

open StateTransition

private abbrev transition := flip Option.bind step

theorem inputCount_phase (state : State) (count offset : Nat)
    (input : List NormalizedCircuitSym) (output : List FormulaSym)
    (saved : Nat) :
    ∃ finalState,
      transition^[count + 1]
        (some (cfg (some .inputCount) state
          (encodeNormalizedNat count ++ input) output offset saved)) =
      some (cfg (some .expectOutput) finalState input
        (.varMark :: .andMark :: output) (offset + count) saved) := by
  induction count generalizing state offset with
  | zero =>
      refine ⟨{ state with inputBuffer := some .fieldEnd }, ?_⟩
      change step (cfg (some .inputCount) state (.fieldEnd :: input) output
        offset saved) = _
      simpa [encodeNormalizedNat] using
        input_count_end_step state input output offset saved
  | succ count ih =>
      have hfirst := input_count_tick_step state
        (encodeNormalizedNat count ++ input) output offset saved
      rcases ih { state with inputBuffer := some .tick } (offset + 1) with
        ⟨finalState, htail⟩
      refine ⟨finalState, ?_⟩
      have hfull := step_then (count + 1) hfirst htail
      simpa [encodeNormalizedNat, List.replicate_succ, List.append_assoc,
        Nat.add_assoc, Nat.add_left_comm, Nat.add_comm] using hfull

theorem gateCount_phase (state : State) (count : Nat)
    (input : List NormalizedCircuitSym) (output : List FormulaSym)
    (inputCount saved : Nat) :
    ∃ finalState,
      transition^[count + 1]
        (some (cfg (some .gateCount) state
          (encodeNormalizedNat count ++ input) output inputCount saved)) =
      some (cfg (some .rows) finalState input output inputCount saved) := by
  induction count generalizing state with
  | zero =>
      refine ⟨{ state with inputBuffer := some .fieldEnd }, ?_⟩
      change step (cfg (some .gateCount) state (.fieldEnd :: input) output
        inputCount saved) = _
      simpa [encodeNormalizedNat] using
        gate_count_end_step state input output inputCount saved
  | succ count ih =>
      have hfirst := gate_count_tick_step state
        (encodeNormalizedNat count ++ input) output inputCount saved
      rcases ih { state with inputBuffer := some .tick } with
        ⟨finalState, htail⟩
      refine ⟨finalState, ?_⟩
      have hfull := step_then (count + 1) hfirst htail
      simpa [encodeNormalizedNat, List.replicate_succ,
        List.append_assoc] using hfull

def headerSteps (c : Circuit) : Nat :=
  1 + 1 + (c.inputCount + 1) + 1 +
    ((2 * c.inputCount + 2) + (c.output + 1)) + 1 +
    (c.gates.length + 1)

/-- Parse a canonical guarded header and emit the outer conjunction and output
variable, leaving exactly the chronological row stream. -/
theorem header_phase (c : Circuit) :
    ∃ finalState,
      transition^[headerSteps c]
        (some (_root_.Turing.initList reverseMachine
          (encodeNormalizedCircuit c))) =
      some (cfg (some .rows) finalState
        (encodeNormalizedGateRowsFrom 0 c.gates)
        ((.andMark :: varEnc (c.inputCount + c.output)).reverse)
        c.inputCount 0) := by
  have hinit : _root_.Turing.initList reverseMachine
      (encodeNormalizedCircuit c) =
      cfg (some .start) initialState (encodeNormalizedCircuit c) [] 0 0 := by
    apply _root_.Turing.TM2Comp.Cfg_ext
    · rfl
    · rfl
    · funext stack
      cases stack <;>
        simp [cfg, reverseMachine, stackContents, _root_.Turing.initList]
  have hstart := start_valid_step initialState
    (.inputCountMark :: encodeNormalizedNat c.inputCount ++
      .outputIndexMark :: encodeNormalizedNat c.output ++
      .gateCountMark :: encodeNormalizedNat c.gates.length ++
      encodeNormalizedGateRowsFrom 0 c.gates) [] 0 0
  have hmarker := expect_input_count_step
    { initialState with inputBuffer := some .validMark }
    (encodeNormalizedNat c.inputCount ++
      .outputIndexMark :: encodeNormalizedNat c.output ++
      .gateCountMark :: encodeNormalizedNat c.gates.length ++
      encodeNormalizedGateRowsFrom 0 c.gates) [] 0 0
  rcases inputCount_phase
      { initialState with inputBuffer := some .inputCountMark }
      c.inputCount 0
      (.outputIndexMark :: encodeNormalizedNat c.output ++
        .gateCountMark :: encodeNormalizedNat c.gates.length ++
        encodeNormalizedGateRowsFrom 0 c.gates) [] 0 with
    ⟨afterCount, hcount⟩
  have houtputMarker := expect_output_step afterCount
    (encodeNormalizedNat c.output ++
      .gateCountMark :: encodeNormalizedNat c.gates.length ++
      encodeNormalizedGateRowsFrom 0 c.gates)
    [.varMark, .andMark] c.inputCount 0
  rcases variable_phase
      { afterCount with inputBuffer := some .outputIndexMark }
      .output c.inputCount c.output
      (.gateCountMark :: encodeNormalizedNat c.gates.length ++
        encodeNormalizedGateRowsFrom 0 c.gates) [.andMark] with
    ⟨afterOutput, houtput⟩
  have hgateMarker := expect_gate_count_step afterOutput
    (encodeNormalizedNat c.gates.length ++
      encodeNormalizedGateRowsFrom 0 c.gates)
    ((varEnc (c.inputCount + c.output)).reverse ++ [.andMark])
    c.inputCount 0
  rcases gateCount_phase
      { afterOutput with inputBuffer := some .gateCountMark }
      c.gates.length (encodeNormalizedGateRowsFrom 0 c.gates)
      ((varEnc (c.inputCount + c.output)).reverse ++ [.andMark])
      c.inputCount 0 with ⟨finalState, hgates⟩
  refine ⟨finalState, ?_⟩
  rw [hinit]
  have h₁ := step_then 0 hstart (by rfl)
  simp only [Nat.zero_add, Function.iterate_zero_apply] at h₁
  have h₂ := step_then 0 hmarker (by rfl)
  simp only [Nat.zero_add, Function.iterate_zero_apply] at h₂
  have h₃ := step_then 0 houtputMarker (by rfl)
  simp only [Nat.zero_add, Function.iterate_zero_apply] at h₃
  have h₄ := step_then 0 hgateMarker (by rfl)
  simp only [Nat.zero_add, Function.iterate_zero_apply] at h₄
  have hcount' := hcount
  simp only [Nat.zero_add, List.append_assoc] at hcount'
  have h₁₂ := step_comp _ _ h₁ h₂
  have h₁₂' :
      transition^[2]
        (some (cfg (some .start) initialState (encodeNormalizedCircuit c)
          [] 0 0)) =
      some (cfg (some .inputCount)
        { initialState with inputBuffer := some .inputCountMark }
        (encodeNormalizedNat c.inputCount ++
          (.outputIndexMark :: (encodeNormalizedNat c.output ++
            (.gateCountMark :: (encodeNormalizedNat c.gates.length ++
              encodeNormalizedGateRowsFrom 0 c.gates))))) [] 0 0) := by
    convert h₁₂ using 1 <;>
      simp [encodeNormalizedCircuit, List.append_assoc]
  have h₁₃ := step_comp _ _ h₁₂' hcount'
  have h₃' :
      transition^[1]
        (some (cfg (some .expectOutput) afterCount
          (.outputIndexMark :: (encodeNormalizedNat c.output ++
            (.gateCountMark :: (encodeNormalizedNat c.gates.length ++
              encodeNormalizedGateRowsFrom 0 c.gates))))
          [.varMark, .andMark] c.inputCount 0)) =
      some (cfg (some (.copyPrefix .output))
        { afterCount with inputBuffer := some .outputIndexMark }
        (encodeNormalizedNat c.output ++
          (.gateCountMark :: (encodeNormalizedNat c.gates.length ++
            encodeNormalizedGateRowsFrom 0 c.gates)))
        [.varMark, .andMark] c.inputCount 0) := by
    convert h₃ using 1 <;> simp [List.append_assoc]
  have h₁₄ := step_comp _ _ h₁₃ h₃'
  have h₁₅ := step_comp _ _ h₁₄ houtput
  have h₁₅' :
      transition^[2 + (c.inputCount + 1) + 1 +
          ((2 * c.inputCount + 2) + (c.output + 1))]
        (some (cfg (some .start) initialState (encodeNormalizedCircuit c)
          [] 0 0)) =
      some (cfg (some .expectGateCount) afterOutput
        (.gateCountMark :: (encodeNormalizedNat c.gates.length ++
          encodeNormalizedGateRowsFrom 0 c.gates))
        ((varEnc (c.inputCount + c.output)).reverse ++ [.andMark])
        c.inputCount 0) := by
    convert h₁₅ using 1 <;>
      simp only [afterOffsetLabel, afterOffsetOutput, varEnc,
        List.replicate_add, List.reverse_cons, List.reverse_append,
        List.reverse_replicate, List.reverse_nil, List.nil_append,
        List.replicate_one,
        List.cons_append, List.append_assoc, Nat.add_assoc]
  have h₁₆ := step_comp _ _ h₁₅' h₄
  have hfull := step_comp _ _ h₁₆ hgates
  have hsteps :
      2 + (c.inputCount + 1) + 1 +
          ((2 * c.inputCount + 2) + (c.output + 1)) + 1 +
          (c.gates.length + 1) = headerSteps c := by
    simp [headerSteps]
  rw [hsteps] at hfull
  simpa only [List.reverse_cons, List.reverse_nil, List.nil_append,
    List.singleton_append, List.append_assoc] using hfull

end CLRS.Chapter34.Turing.GeneralCircuitToSAT.Emitter
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