Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_6c6d3d95ade0edcb4d22e302

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_c9fc920e12cb3e507dd93b3d
import Definitions.Def_PricingWithTips3DM_68c5fb77697279bbfde458e3
import Mathlib.Data.Fin.Tuple.Take
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# List-valued routing of terminal statement stacks

After the heterogeneous action table has been split by stack, the remaining
push/pop semantics can be stated using ordinary lists.  This module records a
stack as its height-wire list and its cell-row list, defines the exact list
transformations for push and pop, and proves agreement with the typed
`StackWires` operations and their sequential fold.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

/-- Ordinary list representation of one stack's complete wire block. -/
@[ext] structure TransitionStackValueBlock where
  heightValues : List Nat
  cellRows : List (List Nat)
deriving DecidableEq, Repr

/-- Read the list representation from typed stack wires. -/
def TransitionStackValueBlock.ofWires
    {tm : _root_.Turing.FinTM2} {height : Nat} {k : tm.K}
    (source : StackWires tm height k) : TransitionStackValueBlock :=
  { heightValues := transitionStackHeightWireValues source
    cellRows := transitionStackCellWireRows source }

/-- Flatten a list-valued stack block in canonical tableau order. -/
def TransitionStackValueBlock.flatten
    (block : TransitionStackValueBlock) : List Nat :=
  block.heightValues ++ block.cellRows.flatten

@[simp] theorem TransitionStackValueBlock.flatten_ofWires
    {tm : _root_.Turing.FinTM2} {height : Nat} {k : tm.K}
    (source : StackWires tm height k) :
    (TransitionStackValueBlock.ofWires source).flatten =
      transitionStackWireValues source := by
  rfl

/-- Exact fixed-capacity list transformation performed by a push. -/
def TransitionStackValueBlock.push
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (height falseWire : Nat) (symbol : SymbolWires tm k)
    (source : TransitionStackValueBlock) : TransitionStackValueBlock :=
  match height with
  | 0 =>
      { heightValues := [falseWire]
        cellRows := [] }
  | previous + 1 =>
      { heightValues := falseWire :: source.heightValues.take (previous + 1)
        cellRows := transitionPushedSymbolWireRow tm k falseWire symbol ::
          source.cellRows.take previous }

/-- Exact fixed-capacity list transformation performed by a pop. -/
def TransitionStackValueBlock.pop
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (height falseWire trueWire start : Nat)
    (source : TransitionStackValueBlock) : TransitionStackValueBlock :=
  match height with
  | 0 => source
  | _ + 1 =>
      { heightValues := start :: source.heightValues.drop 2 ++ [falseWire]
        cellRows := source.cellRows.drop 1 ++
          [transitionBlankSymbolWireRow tm k falseWire trueWire] }

private theorem transitionStackHeightWireValues_take_castSucc
    (tm : _root_.Turing.FinTM2) (k : tm.K) (height : Nat)
    (source : StackWires tm height.succ k) :
    (transitionStackHeightWireValues source).take height.succ =
      List.ofFn (fun index : Fin height.succ =>
        source.height index.castSucc) := by
  unfold transitionStackHeightWireValues
  rw [← Fin.ofFn_take_eq_take_ofFn (m := height.succ) (by omega)
    source.height]
  apply List.ofFn_inj.mpr
  funext index
  rfl

private theorem transitionStackCellWireRows_take
    (tm : _root_.Turing.FinTM2) (k : tm.K) (height : Nat)
    (source : StackWires tm height.succ k) :
    (transitionStackCellWireRows source).take height =
      List.ofFn (fun cell : Fin height =>
        List.ofFn (source.cell cell.castSucc)) := by
  unfold transitionStackCellWireRows
  rw [← Fin.ofFn_take_eq_take_ofFn (m := height) (by omega)
    (fun cell : Fin height.succ => List.ofFn (source.cell cell))]
  apply List.ofFn_inj.mpr
  funext cell
  rfl

private theorem transitionStackHeightWireValues_drop_two
    (tm : _root_.Turing.FinTM2) (k : tm.K) (height : Nat)
    (source : StackWires tm height.succ k) :
    (transitionStackHeightWireValues source).drop 2 =
      List.ofFn (fun index : Fin height =>
        source.height ⟨index.val + 2, by omega⟩) := by
  apply List.ext_get
  · simp [transitionStackHeightWireValues]
  · intro index hleft hright
    simp [transitionStackHeightWireValues]

private theorem transitionStackCellWireRows_drop_one
    (tm : _root_.Turing.FinTM2) (k : tm.K) (height : Nat)
    (source : StackWires tm height.succ k) :
    (transitionStackCellWireRows source).drop 1 =
      List.ofFn (fun cell : Fin height =>
        List.ofFn (source.cell cell.succ)) := by
  apply List.ext_get
  · simp [transitionStackCellWireRows]
  · intro index hleft hright
    simp [transitionStackCellWireRows]

/-- The typed push operation is exactly the ordinary list transformation. -/
theorem TransitionStackValueBlock.ofWires_push
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (height falseWire : Nat) (symbol : SymbolWires tm k)
    (source : StackWires tm height k) :
    TransitionStackValueBlock.ofWires
        (arithmeticPushStackWires tm k falseWire symbol height source) =
      (TransitionStackValueBlock.ofWires source).push tm k height falseWire
        symbol := by
  cases height with
  | zero =>
      apply TransitionStackValueBlock.ext <;>
        simp [TransitionStackValueBlock.ofWires,
          TransitionStackValueBlock.push,
          transitionStackHeightWireValues, transitionStackCellWireRows,
          arithmeticPushStackWires]
  | succ height =>
      apply TransitionStackValueBlock.ext
      · simp only [TransitionStackValueBlock.ofWires,
          TransitionStackValueBlock.push]
        rw [arithmeticPushStackWires_height_values]
        rw [transitionStackHeightWireValues_take_castSucc]
      · simp only [TransitionStackValueBlock.ofWires,
          TransitionStackValueBlock.push]
        rw [arithmeticPushStackWires_cell_rows]
        rw [transitionStackCellWireRows_take]

/-- The typed pop operation is exactly the ordinary list transformation. -/
theorem TransitionStackValueBlock.ofWires_pop
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (height falseWire trueWire start : Nat)
    (source : StackWires tm height k) :
    TransitionStackValueBlock.ofWires
        (arithmeticPopStackWires tm k falseWire trueWire start height source) =
      (TransitionStackValueBlock.ofWires source).pop tm k height falseWire
        trueWire start := by
  cases height with
  | zero => rfl
  | succ height =>
      apply TransitionStackValueBlock.ext
      · simp only [TransitionStackValueBlock.ofWires,
          TransitionStackValueBlock.pop]
        rw [arithmeticPopStackWires_height_values]
        rw [transitionStackHeightWireValues_drop_two]
        simp [List.concat_eq_append]
      · simp only [TransitionStackValueBlock.ofWires,
          TransitionStackValueBlock.pop]
        rw [arithmeticPopStackWires_cell_rows]
        rw [transitionStackCellWireRows_drop_one]
        simp [List.concat_eq_append]

/-- List-valued semantics of one selected-stack action. -/
def TransitionStmtSelectedStackAction.evalValues
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (originStart height falseWire trueWire : Nat)
    (source : TransitionStackValueBlock) :
    TransitionStmtSelectedStackAction tm k → TransitionStackValueBlock
  | .push symbolOffsets =>
      source.push tm k height falseWire
        (fun target => originStart + (symbolOffsets target).eval height)
  | .pop heightWireOffset =>
      source.pop tm k height falseWire trueWire
        (originStart + heightWireOffset.eval height)

/-- One selected action commutes with erasing typed wires to ordinary lists. -/
theorem TransitionStmtSelectedStackAction.ofWires_eval
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (originStart height falseWire trueWire : Nat)
    (source : StackWires tm height k)
    (action : TransitionStmtSelectedStackAction tm k) :
    TransitionStackValueBlock.ofWires
        (action.eval tm k originStart height falseWire trueWire source) =
      action.evalValues tm k originStart height falseWire trueWire
        (TransitionStackValueBlock.ofWires source) := by
  cases action with
  | push symbolOffsets =>
      exact TransitionStackValueBlock.ofWires_push tm k height falseWire _
        source
  | pop heightWireOffset =>
      exact TransitionStackValueBlock.ofWires_pop tm k height falseWire
        trueWire _ source

/-- Sequential list-valued execution of one stack's action subsequence. -/
def transitionStmtSelectedStackActionValues_eval
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (originStart height falseWire trueWire : Nat)
    (source : TransitionStackValueBlock)
    (actions : List (TransitionStmtSelectedStackAction tm k)) :
    TransitionStackValueBlock :=
  actions.foldl
    (fun current action =>
      action.evalValues tm k originStart height falseWire trueWire current)
    source

/-- Erasing typed stack wires commutes with the complete selected action fold. -/
theorem transitionStmtSelectedStackActions_eval_values
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (originStart height falseWire trueWire : Nat)
    (source : StackWires tm height k)
    (actions : List (TransitionStmtSelectedStackAction tm k)) :
    TransitionStackValueBlock.ofWires
        (transitionStmtSelectedStackActions_eval tm k originStart height
          falseWire trueWire source actions) =
      transitionStmtSelectedStackActionValues_eval tm k originStart height
        falseWire trueWire (TransitionStackValueBlock.ofWires source)
        actions := by
  induction actions generalizing source with
  | nil => rfl
  | cons action rest ih =>
      change TransitionStackValueBlock.ofWires
          (transitionStmtSelectedStackActions_eval tm k originStart height
            falseWire trueWire
            (action.eval tm k originStart height falseWire trueWire source)
            rest) = _
      rw [ih]
      rw [action.ofWires_eval tm k originStart height falseWire trueWire
        source]
      rfl

/-- Canonical flat values of a projected global action fold are exactly the
flattened result of its independent list-valued stack route. -/
theorem transitionStmtStackActions_eval_stack_values
    (tm : _root_.Turing.FinTM2) (target : tm.K)
    (originStart height falseWire trueWire : Nat)
    (source : CfgWires tm height)
    (actions : List (TransitionStmtStackAction tm)) :
    transitionStackWireValues
        ((transitionStmtStackActions_eval tm originStart height falseWire
          trueWire source actions).stack target) =
      (transitionStmtSelectedStackActionValues_eval tm target originStart
        height falseWire trueWire
        (TransitionStackValueBlock.ofWires (source.stack target))
        (transitionStmtStackActionsFor tm target actions)).flatten := by
  rw [transitionStmtStackActions_eval_stack_eq_selected]
  rw [← TransitionStackValueBlock.flatten_ofWires]
  rw [transitionStmtSelectedStackActions_eval_values]

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