Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.CookLevin.Circuitization.GeneratorTransitionStatementAffineContextRecursiveDispatch

Definition
PricingWithTips3DM_783d3418d327b57f6627754d

by qmaai2907271020 · Oct 23, 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_6890a8cc8d21d05e1c974e9b
import Definitions.Def_PricingWithTips3DM_bedc98df39f74f59e866c0e6
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Recursive statements reconnected to complete label dispatch

Each program label contributes its recursively generated statement followed
immediately by the outer label-selector mux.  This module restores that exact
interleaving and proves equality with `transitionDispatchScriptFromSeed`, the
canonical complete dispatch field of one local transition.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- Generic progression-controller output for one outer label mux. -/
def TransitionDispatchLabelArtifact.recursiveMuxControllerFrames
    {tm : _root_.Turing.FinTM2}
    (artifact : TransitionDispatchLabelArtifact tm) : List UnaryFrameSym :=
  affineStmtPhaseTagCode (.mux artifact.selector artifact.muxFrames) ++
    affineMuxInvocationProgressionFamilyFrames artifact.muxInvocationSegments

/-- When the artifact's frames are canonical, the generic mux controller
produces exactly the statement-controller encoding of its outer mux phase. -/
theorem TransitionDispatchLabelArtifact.recursiveMuxControllerFrames_eq
    {tm : _root_.Turing.FinTM2}
    (artifact : TransitionDispatchLabelArtifact tm)
    (hselector : ∀ frame ∈ artifact.muxFrames,
      frame.selector = artifact.selector)
    (hfalseArm : ∀ frame ∈ artifact.muxFrames,
      frame.falseArm = frame.trueArm + 1) :
    artifact.recursiveMuxControllerFrames =
      encodeAffineStmtControllerScript
        [.mux artifact.selector artifact.muxFrames] := by
  unfold TransitionDispatchLabelArtifact.recursiveMuxControllerFrames
    TransitionDispatchLabelArtifact.muxInvocationSegments
  rw [affineMuxInvocationSingletonSegments_frames artifact.selector
    artifact.muxFrames hselector hfalseArm]
  simp [encodeAffineStmtControllerScript, encodeAffineStmtControllerPhase,
    affineStmtPhasePayload]

/-- Recursive statements and outer muxes, interleaved for a fixed label
suffix. -/
noncomputable def transitionDispatchRecursiveControllerFramesForLabels
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (source : CfgWires tm (workHeight tm seed.height)) :
    TransitionAffineNat → Nat → CfgWires tm (workHeight tm seed.height) →
      List tm.Λ → List UnaryFrameSym
  | _, _, _, [] => []
  | labelOffset, start, fallback, label :: labels =>
      let statement := transitionStmtScript tm (workHeight tm seed.height)
        seed.start (seed.start + 1) start source (tm.m label)
        (stmtPushSet_program_subset tm label)
      let statementWires := transitionStmtOutputWires tm
        (workHeight tm seed.height) seed.start (seed.start + 1) start source
        (tm.m label) (stmtPushSet_program_subset tm label)
      let selector := source.label (Fin.castSucc (labelEquivFin tm label))
      let muxStart := start + compileStmtGateCost tm
        (workHeight tm seed.height) (tm.m label)
      let artifact : TransitionDispatchLabelArtifact tm :=
        { label := label
          start := start
          statement := statement
          selector := selector
          muxFrames := affineMuxFinCanonicalFrames muxStart selector _
            (fun coordinate => statementWires
              ((cfgSlotEquivFin tm (workHeight tm seed.height)).symm
                coordinate))
            (fun coordinate => fallback
              ((cfgSlotEquivFin tm (workHeight tm seed.height)).symm
                coordinate)) }
      transitionStmtRecursiveControllerFrames tm seed labelOffset
          (TransitionStmtAffineContext.initial tm) (tm.m label)
          (stmtPushSet_program_subset tm label) ++
        artifact.recursiveMuxControllerFrames ++
        transitionDispatchRecursiveControllerFramesForLabels tm seed source
          ((labelOffset.add (transitionDispatchStmtGateAffine tm label)).add
            (transitionDispatchMuxGateAffine tm))
          (muxStart +
            (3 * cfgBitCount tm (workHeight tm seed.height) + 1))
          (arithmeticMuxCfgWires tm (workHeight tm seed.height) muxStart)
          labels

/-- Complete seed-local controller output for the entire label dispatch. -/
def transitionDispatchRecursiveControllerFramesFromSeed
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    List UnaryFrameSym :=
  let source := arithmeticWidenedCfgWires tm seed.height seed.start seed.rowBase
  transitionDispatchRecursiveControllerFramesForLabels tm seed source
    (TransitionAffineNat.const 2) (seed.start + 2) source (programLabels tm)

/-- Label-suffix reassembly agrees with the builder-free artifact recursion. -/
theorem
    verifierTransitionDispatchRecursiveControllerFramesForLabels_eq_script
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) (seed : TransitionRowSeed)
    (hseed : seed.height = (verifierHeight W).eval input.length) :
    let source := arithmeticWidenedCfgWires W.machine.tm seed.height
      seed.start seed.rowBase
    ∀ (labelOffset : TransitionAffineNat) (start : Nat)
      (fallback : CfgWires W.machine.tm
        (workHeight W.machine.tm seed.height))
      (labels : List W.machine.tm.Λ),
      start = seed.start + labelOffset.eval seed.height →
      transitionDispatchRecursiveControllerFramesForLabels W.machine.tm seed
          source labelOffset start fallback labels =
        encodeAffineStmtControllerScript
          ((transitionDispatchLabelArtifacts W.machine.tm seed.height
            seed.start (seed.start + 1) source start fallback labels).flatMap
              TransitionDispatchLabelArtifact.script) := by
  dsimp only
  intro labelOffset start fallback labels hstart
  induction labels generalizing labelOffset start fallback with
  | nil => rfl
  | cons label labels ih =>
      let source := arithmeticWidenedCfgWires W.machine.tm seed.height
        seed.start seed.rowBase
      let statement := transitionStmtScript W.machine.tm
        (workHeight W.machine.tm seed.height) seed.start (seed.start + 1)
        start source (W.machine.tm.m label)
        (stmtPushSet_program_subset W.machine.tm label)
      let statementWires := transitionStmtOutputWires W.machine.tm
        (workHeight W.machine.tm seed.height) seed.start (seed.start + 1)
        start source (W.machine.tm.m label)
        (stmtPushSet_program_subset W.machine.tm label)
      let selector := source.label
        (Fin.castSucc (labelEquivFin W.machine.tm label))
      let muxStart := start + compileStmtGateCost W.machine.tm
        (workHeight W.machine.tm seed.height) (W.machine.tm.m label)
      let artifact : TransitionDispatchLabelArtifact W.machine.tm :=
        { label := label
          start := start
          statement := statement
          selector := selector
          muxFrames := affineMuxFinCanonicalFrames muxStart selector _
            (fun coordinate => statementWires
              ((cfgSlotEquivFin W.machine.tm
                (workHeight W.machine.tm seed.height)).symm coordinate))
            (fun coordinate => fallback
              ((cfgSlotEquivFin W.machine.tm
                (workHeight W.machine.tm seed.height)).symm coordinate)) }
      have hstatement :=
        transitionStmtRecursiveInitialControllerFrames_eq_script W input seed
          hseed labelOffset label
      rw [← hstart] at hstatement
      have hmux : artifact.recursiveMuxControllerFrames =
          encodeAffineStmtControllerScript
            [.mux artifact.selector artifact.muxFrames] := by
        apply artifact.recursiveMuxControllerFrames_eq
        · exact affineMuxFinCanonicalFrames_selector _ _ _ _ _
        · exact affineMuxFinCanonicalFrames_falseArm _ _ _ _ _
      have hheight : 0 < seed.height := by
        rw [hseed]
        exact verifierHeight_eval_pos W input.length
      have hnextStart :
          muxStart +
              (3 * cfgBitCount W.machine.tm
                (workHeight W.machine.tm seed.height) + 1) =
            seed.start +
              (((labelOffset.add
                (transitionDispatchStmtGateAffine W.machine.tm label)).add
                  (transitionDispatchMuxGateAffine W.machine.tm)).eval
                    seed.height) := by
        rw [TransitionAffineNat.eval_add, TransitionAffineNat.eval_add,
          transitionDispatchStmtGateAffine_eval W.machine.tm label
            seed.height
            (Nat.add_pos_left hheight
              (maxPushesPerStep W.machine.tm)),
          transitionDispatchMuxGateAffine_eval]
        simp only [muxStart]
        omega
      have htail := ih
        (((labelOffset.add
          (transitionDispatchStmtGateAffine W.machine.tm label)).add
            (transitionDispatchMuxGateAffine W.machine.tm)))
        (muxStart +
          (3 * cfgBitCount W.machine.tm
            (workHeight W.machine.tm seed.height) + 1))
        (arithmeticMuxCfgWires W.machine.tm
          (workHeight W.machine.tm seed.height) muxStart)
        hnextStart
      simp only [transitionDispatchRecursiveControllerFramesForLabels,
        transitionDispatchLabelArtifacts, List.flatMap_cons,
        TransitionDispatchLabelArtifact.script]
      change _ ++ artifact.recursiveMuxControllerFrames ++ _ = _
      rw [hstatement, hmux, htail]
      simp [encodeAffineStmtControllerScript,
        encodeAffineStmtControllerPhase, List.flatMap_append,
        List.append_assoc]
      rfl

/-- Complete seed-local dispatch closure. -/
theorem verifierTransitionDispatchRecursiveControllerFramesFromSeed_eq_script
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) (seed : TransitionRowSeed)
    (hseed : seed.height = (verifierHeight W).eval input.length) :
    transitionDispatchRecursiveControllerFramesFromSeed W.machine.tm seed =
      encodeAffineStmtControllerScript
        (transitionDispatchScriptFromSeed W.machine.tm seed) := by
  unfold transitionDispatchRecursiveControllerFramesFromSeed
    transitionDispatchScriptFromSeed transitionDispatchArtifactsFromSeed
  exact
    verifierTransitionDispatchRecursiveControllerFramesForLabels_eq_script
      W input seed hseed (TransitionAffineNat.const 2) (seed.start + 2)
      (arithmeticWidenedCfgWires W.machine.tm seed.height seed.start
        seed.rowBase)
      (programLabels W.machine.tm) (by simp [TransitionAffineNat.eval_const])

/-- Row-major complete dispatch output of the recursive controllers. -/
def verifierTransitionRecursiveDispatchControllerTarget
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List UnaryFrameSym :=
  (verifierTransitionRowSeeds W input).flatMap
    (transitionDispatchRecursiveControllerFramesFromSeed W.machine.tm)

/-- Row-major semantic encoding of every complete label dispatch. -/
def verifierTransitionRecursiveDispatchSemanticTarget
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List UnaryFrameSym :=
  (verifierTransitionRowSeeds W input).flatMap fun seed =>
    encodeAffineStmtControllerScript
      (transitionDispatchScriptFromSeed W.machine.tm seed)

/-- Every statement and outer label mux of every transition row is generated
in the exact canonical order. -/
theorem verifierTransitionRecursiveDispatchControllerTarget_eq
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierTransitionRecursiveDispatchControllerTarget W input =
      verifierTransitionRecursiveDispatchSemanticTarget W input := by
  unfold verifierTransitionRecursiveDispatchControllerTarget
    verifierTransitionRecursiveDispatchSemanticTarget
  apply List.flatMap_congr
  intro seed hseed
  apply verifierTransitionDispatchRecursiveControllerFramesFromSeed_eq_script
    W input seed
  exact verifierTransitionRowSeeds_height_eq W input seed hseed

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