Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_a0d13e16a04e1fa3c4d79a91

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

/-!
# Static atoms for sequential statement stack routing

A terminal statement may update the same stack more than once.  Running each
primitive compiler from the original tableau row is therefore insufficient:
later actions must observe earlier actions.  This module removes that dynamic
dependency.  Every final coordinate is first normalized to either a reference
to the original stack or a constant wire/row.  Interpreting the normalized
atoms once is proved equal to the original sequential push/pop fold.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

/-- One statically routed output coordinate: either read an original source
coordinate or emit a constant value. -/
inductive TransitionRouteAtom (α : Type)
  | source (index : Nat)
  | const (value : α)
deriving DecidableEq, Repr

/-- Interpret one route atom.  The fallback is irrelevant for atoms produced
from a source list, because all such indices are in range. -/
def TransitionRouteAtom.eval (fallback : α) (source : List α) :
    TransitionRouteAtom α → α
  | .source index => source.getD index fallback
  | .const value => value

/-- Pointwise interpretation of a static route. -/
def transitionRouteAtomsEval (fallback : α) (source : List α)
    (atoms : List (TransitionRouteAtom α)) : List α :=
  atoms.map (TransitionRouteAtom.eval fallback source)

/-- Identity route over every coordinate of `source`. -/
def transitionRouteSourceAtoms (source : List α) :
    List (TransitionRouteAtom α) :=
  (List.range source.length).map TransitionRouteAtom.source

/-- Interpreting the identity route recovers the exact source list. -/
@[simp] theorem transitionRouteAtomsEval_source
    (fallback : α) (source : List α) :
    transitionRouteAtomsEval fallback source
      (transitionRouteSourceAtoms source) = source := by
  apply List.ext_get
  · simp [transitionRouteAtomsEval, transitionRouteSourceAtoms]
  · intro index hleft hright
    simp [transitionRouteAtomsEval, transitionRouteSourceAtoms,
      TransitionRouteAtom.eval, List.getD_eq_getElem?_getD, hright]

/-- Static route atoms for both components of one stack block. -/
@[ext] structure TransitionStackRouteAtomBlock where
  heightAtoms : List (TransitionRouteAtom Nat)
  cellAtoms : List (TransitionRouteAtom (List Nat))
deriving DecidableEq, Repr

/-- Identity atom block for one concrete source block. -/
def TransitionStackRouteAtomBlock.ofSource
    (source : TransitionStackValueBlock) : TransitionStackRouteAtomBlock :=
  { heightAtoms := transitionRouteSourceAtoms source.heightValues
    cellAtoms := transitionRouteSourceAtoms source.cellRows }

/-- Interpret a static atom block against the original stack block. -/
def TransitionStackRouteAtomBlock.eval
    (source : TransitionStackValueBlock)
    (route : TransitionStackRouteAtomBlock) : TransitionStackValueBlock :=
  { heightValues :=
      transitionRouteAtomsEval 0 source.heightValues route.heightAtoms
    cellRows :=
      transitionRouteAtomsEval [] source.cellRows route.cellAtoms }

/-- The identity atom block denotes its source exactly. -/
@[simp] theorem TransitionStackRouteAtomBlock.ofSource_eval
    (source : TransitionStackValueBlock) :
    (TransitionStackRouteAtomBlock.ofSource source).eval source = source := by
  apply TransitionStackValueBlock.ext <;>
    simp [TransitionStackRouteAtomBlock.eval,
      TransitionStackRouteAtomBlock.ofSource]

/-- Static atom transformation corresponding to one fixed-capacity push. -/
def TransitionStackRouteAtomBlock.push
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (height falseWire : Nat) (symbol : SymbolWires tm k)
    (route : TransitionStackRouteAtomBlock) :
    TransitionStackRouteAtomBlock :=
  match height with
  | 0 =>
      { heightAtoms := [.const falseWire]
        cellAtoms := [] }
  | previous + 1 =>
      { heightAtoms :=
          .const falseWire :: route.heightAtoms.take (previous + 1)
        cellAtoms :=
          .const (transitionPushedSymbolWireRow tm k falseWire symbol) ::
            route.cellAtoms.take previous }

/-- Static atom transformation corresponding to one fixed-capacity pop. -/
def TransitionStackRouteAtomBlock.pop
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (height falseWire trueWire start : Nat)
    (route : TransitionStackRouteAtomBlock) :
    TransitionStackRouteAtomBlock :=
  match height with
  | 0 => route
  | _ + 1 =>
      { heightAtoms :=
          .const start :: route.heightAtoms.drop 2 ++ [.const falseWire]
        cellAtoms := route.cellAtoms.drop 1 ++
          [.const (transitionBlankSymbolWireRow tm k falseWire trueWire)] }

/-- Static push normalization commutes with interpreting route atoms. -/
theorem TransitionStackRouteAtomBlock.eval_push
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (height falseWire : Nat) (symbol : SymbolWires tm k)
    (source : TransitionStackValueBlock)
    (route : TransitionStackRouteAtomBlock) :
    (route.push tm k height falseWire symbol).eval source =
      (route.eval source).push tm k height falseWire symbol := by
  cases height with
  | zero =>
      apply TransitionStackValueBlock.ext <;>
        simp [TransitionStackRouteAtomBlock.push,
          TransitionStackRouteAtomBlock.eval,
          TransitionStackValueBlock.push, transitionRouteAtomsEval,
          TransitionRouteAtom.eval]
  | succ height =>
      apply TransitionStackValueBlock.ext <;>
        simp [TransitionStackRouteAtomBlock.push,
          TransitionStackRouteAtomBlock.eval,
          TransitionStackValueBlock.push, transitionRouteAtomsEval,
          TransitionRouteAtom.eval]

/-- Static pop normalization commutes with interpreting route atoms. -/
theorem TransitionStackRouteAtomBlock.eval_pop
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (height falseWire trueWire start : Nat)
    (source : TransitionStackValueBlock)
    (route : TransitionStackRouteAtomBlock) :
    (route.pop tm k height falseWire trueWire start).eval source =
      (route.eval source).pop tm k height falseWire trueWire start := by
  cases height with
  | zero => rfl
  | succ height =>
      apply TransitionStackValueBlock.ext <;>
        simp [TransitionStackRouteAtomBlock.pop,
          TransitionStackRouteAtomBlock.eval,
          TransitionStackValueBlock.pop, transitionRouteAtomsEval,
          TransitionRouteAtom.eval, List.map_append]

/-- Apply one selected statement action to static route atoms. -/
def TransitionStmtSelectedStackAction.evalAtoms
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (originStart height falseWire trueWire : Nat)
    (route : TransitionStackRouteAtomBlock) :
    TransitionStmtSelectedStackAction tm k → TransitionStackRouteAtomBlock
  | .push symbolOffsets =>
      route.push tm k height falseWire
        (fun target => originStart + (symbolOffsets target).eval height)
  | .pop heightWireOffset =>
      route.pop tm k height falseWire trueWire
        (originStart + heightWireOffset.eval height)

/-- Interpreting one normalized action agrees with its list-valued semantics. -/
theorem TransitionStmtSelectedStackAction.evalAtoms_eval
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (originStart height falseWire trueWire : Nat)
    (source : TransitionStackValueBlock)
    (route : TransitionStackRouteAtomBlock)
    (action : TransitionStmtSelectedStackAction tm k) :
    (action.evalAtoms tm k originStart height falseWire trueWire route).eval
        source =
      action.evalValues tm k originStart height falseWire trueWire
        (route.eval source) := by
  cases action with
  | push symbolOffsets =>
      exact route.eval_push tm k height falseWire _ source
  | pop heightWireOffset =>
      exact route.eval_pop tm k height falseWire trueWire _ source

/-- Sequential normalization of a selected stack's complete action table. -/
def transitionStmtSelectedStackActionAtoms
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (originStart height falseWire trueWire : Nat)
    (route : TransitionStackRouteAtomBlock)
    (actions : List (TransitionStmtSelectedStackAction tm k)) :
    TransitionStackRouteAtomBlock :=
  actions.foldl
    (fun current action =>
      action.evalAtoms tm k originStart height falseWire trueWire current)
    route

/-- The complete normalized action fold denotes exactly the original
sequential list-valued stack transformation. -/
theorem transitionStmtSelectedStackActionAtoms_eval_from
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (originStart height falseWire trueWire : Nat)
    (source : TransitionStackValueBlock)
    (route : TransitionStackRouteAtomBlock)
    (actions : List (TransitionStmtSelectedStackAction tm k)) :
    (transitionStmtSelectedStackActionAtoms tm k originStart height falseWire
        trueWire route actions).eval source =
      transitionStmtSelectedStackActionValues_eval tm k originStart height
        falseWire trueWire (route.eval source) actions := by
  induction actions generalizing route with
  | nil => rfl
  | cons action rest ih =>
      change (transitionStmtSelectedStackActionAtoms tm k originStart height
          falseWire trueWire
          (action.evalAtoms tm k originStart height falseWire trueWire route)
          rest).eval source = _
      rw [ih]
      rw [action.evalAtoms_eval tm k originStart height falseWire trueWire
        source route]
      rfl

/-- Starting from the identity atoms, the normalized action table evaluates
to the exact selected-stack semantic fold. -/
theorem transitionStmtSelectedStackActionAtoms_eval
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (originStart height falseWire trueWire : Nat)
    (source : TransitionStackValueBlock)
    (actions : List (TransitionStmtSelectedStackAction tm k)) :
    (transitionStmtSelectedStackActionAtoms tm k originStart height falseWire
        trueWire (TransitionStackRouteAtomBlock.ofSource source) actions).eval
        source =
      transitionStmtSelectedStackActionValues_eval tm k originStart height
        falseWire trueWire source actions := by
  rw [transitionStmtSelectedStackActionAtoms_eval_from]
  rw [TransitionStackRouteAtomBlock.ofSource_eval]

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