Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_6c65e964c341e01e5d179d87

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

/-!
# Canonical true-arm rows of transition dispatch muxes

Every label's `whenTrue` row is the complete output bundle of its fixed
recursive TM2 statement.  This module extracts that row from actual mux
frames and proves exact agreement with the builder-free
`transitionStmtOutputWires` recursion.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- True-input row extracted from one proof-carrying label artifact. -/
def TransitionDispatchLabelArtifact.muxTrueInputValues
    {tm : _root_.Turing.FinTM2}
    (artifact : TransitionDispatchLabelArtifact tm) : List Nat :=
  artifact.muxFrames.map fun frame => frame.whenTrue

/-- Canonical mux frames preserve their true-input function in coordinate
order. -/
theorem affineMuxFinCanonicalFrames_whenTrue_values
    (start selector width : Nat)
    (whenTrue whenFalse : Fin width → CircuitBuilder.Wire) :
    (affineMuxFinCanonicalFrames start selector width
        whenTrue whenFalse).map (fun frame => frame.whenTrue) =
      List.ofFn whenTrue := by
  induction width with
  | zero => rfl
  | succ width ih =>
      simp only [affineMuxFinCanonicalFrames, List.map_append,
        List.map_singleton]
      rw [ih]
      rw [List.ofFn_succ']
      simp [List.concat_eq_append]

/-- Builder-free row recurrence for the statement output of every fixed
program label. -/
def transitionDispatchTrueArmRowsForLabels
    (tm : _root_.Turing.FinTM2) (height falseWire trueWire : Nat)
    (source : CfgWires tm (workHeight tm height)) :
    Nat → List tm.Λ → List (List Nat)
  | _, [] => []
  | start, label :: labels =>
      transitionCfgWireValues tm (workHeight tm height)
          (transitionStmtOutputWires tm (workHeight tm height)
            falseWire trueWire start source (tm.m label)
            (stmtPushSet_program_subset tm label)) ::
        transitionDispatchTrueArmRowsForLabels tm height falseWire trueWire
          source
          (start + compileStmtGateCost tm (workHeight tm height)
              (tm.m label) +
            (3 * cfgBitCount tm (workHeight tm height) + 1))
          labels

/-- Complete seed-only true-arm row family. -/
def transitionDispatchTrueArmRowsFromSeed
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    List (List Nat) :=
  transitionDispatchTrueArmRowsForLabels tm seed.height seed.start
    (seed.start + 1)
    (arithmeticWidenedCfgWires tm seed.height seed.start seed.rowBase)
    (seed.start + 2) (programLabels tm)

/-- Builder-free label artifacts carry exactly the recursive statement output
rows in their true-input fields. -/
theorem transitionDispatchLabelArtifacts_trueArmRows
    (tm : _root_.Turing.FinTM2) (height falseWire trueWire : Nat)
    (source : CfgWires tm (workHeight tm height))
    (start : Nat) (fallback : CfgWires tm (workHeight tm height))
    (labels : List tm.Λ) :
    (transitionDispatchLabelArtifacts tm height falseWire trueWire source
        start fallback labels).map
          TransitionDispatchLabelArtifact.muxTrueInputValues =
      transitionDispatchTrueArmRowsForLabels tm height falseWire trueWire
        source start labels := by
  induction labels generalizing start fallback with
  | nil => rfl
  | cons label labels ih =>
      simp only [transitionDispatchLabelArtifacts,
        transitionDispatchTrueArmRowsForLabels, List.map_cons]
      congr 1
      · unfold TransitionDispatchLabelArtifact.muxTrueInputValues
        rw [affineMuxFinCanonicalFrames_whenTrue_values]
        rfl
      · exact ih _ _

/-- Seed-derived artifacts have exactly the seed-only true-arm family. -/
theorem transitionDispatchArtifactsFromSeed_trueArmRows
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    (transitionDispatchArtifactsFromSeed tm seed).map
        TransitionDispatchLabelArtifact.muxTrueInputValues =
      transitionDispatchTrueArmRowsFromSeed tm seed := by
  unfold transitionDispatchArtifactsFromSeed
    transitionDispatchTrueArmRowsFromSeed
  exact transitionDispatchLabelArtifacts_trueArmRows tm seed.height
    seed.start (seed.start + 1)
    (arithmeticWidenedCfgWires tm seed.height seed.start seed.rowBase)
    (seed.start + 2)
    (arithmeticWidenedCfgWires tm seed.height seed.start seed.rowBase)
    (programLabels tm)

/-- The original proof-carrying widening/dispatch pipeline has the same
true-arm rows as the seed-only recurrence. -/
theorem arithmeticWidening_dispatchArtifact_trueArmRows_eq_seed
    (tm : _root_.Turing.FinTM2) (height rowBase : Nat)
    (base : CircuitBuilder)
    (hvalid : (arithmeticCfgWires tm height rowBase).ValidIn base) :
    let widened := widenCfg base (arithmeticCfgWires tm height rowBase) hvalid
    (compileDispatchArtifacts tm height widened.builder widened.constants
        widened.wires widened.valid).map
          TransitionDispatchLabelArtifact.muxTrueInputValues =
      transitionDispatchTrueArmRowsFromSeed tm
        { height := height, start := base.gates.length,
          rowBase := rowBase } := by
  dsimp only
  rw [arithmeticWidening_dispatchArtifacts_eq_seed]
  exact transitionDispatchArtifactsFromSeed_trueArmRows tm
    { height := height, start := base.gates.length, rowBase := rowBase }

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