Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_68256059a3447c2893af340b

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_4bc768e3be9f86ad3801aa72
import Definitions.Def_PricingWithTips3DM_c9fc920e12cb3e507dd93b3d
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Push bounds for terminal statement stack routes

The terminal statement normal form records a fixed heterogeneous stack-action
table.  This module counts the pushes aimed at one selected stack, proves that
filtering the table by stack preserves that count, and identifies the result
with the existing semantic bound `stmtMaxPushes`.  Consequently every terminal
row produced from a machine label fits in the one-step workspace.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

/-- Contribution of one global stack action to the push count of `target`. -/
def TransitionStmtStackAction.pushCountFor
    (tm : _root_.Turing.FinTM2) (target : tm.K) :
    TransitionStmtStackAction tm → Nat
  | ⟨selected, .push _⟩ => if selected = target then 1 else 0
  | ⟨_, .pop _⟩ => 0

/-- Number of pushes aimed at one stack in a heterogeneous action table. -/
def transitionStmtStackActionPushCountFor
    (tm : _root_.Turing.FinTM2) (target : tm.K) :
    List (TransitionStmtStackAction tm) → Nat
  | [] => 0
  | action :: rest =>
      action.pushCountFor tm target +
        transitionStmtStackActionPushCountFor tm target rest

/-- Push contribution of an action whose selected stack is already fixed. -/
def TransitionStmtSelectedStackAction.pushCount
    (tm : _root_.Turing.FinTM2) (k : tm.K) :
    TransitionStmtSelectedStackAction tm k → Nat
  | .push _ => 1
  | .pop _ => 0

/-- Push count in a per-stack filtered action table. -/
def transitionStmtSelectedStackActionPushCount
    (tm : _root_.Turing.FinTM2) (k : tm.K) :
    List (TransitionStmtSelectedStackAction tm k) → Nat
  | [] => 0
  | action :: rest =>
      action.pushCount tm k +
        transitionStmtSelectedStackActionPushCount tm k rest

/-- Contribution of one heterogeneous action to the total number of actions
aimed at `target`. -/
def TransitionStmtStackAction.actionCountFor
    (tm : _root_.Turing.FinTM2) (target : tm.K)
    (action : TransitionStmtStackAction tm) : Nat :=
  if action.k = target then 1 else 0

/-- Total number of push or pop actions aimed at one stack. -/
def transitionStmtStackActionCountFor
    (tm : _root_.Turing.FinTM2) (target : tm.K) :
    List (TransitionStmtStackAction tm) → Nat
  | [] => 0
  | action :: rest =>
      action.actionCountFor tm target +
        transitionStmtStackActionCountFor tm target rest

/-- Filtering the heterogeneous action table for one stack preserves exactly
the number of commands aimed at that stack. -/
theorem transitionStmtStackActionsFor_length_eq
    (tm : _root_.Turing.FinTM2) (target : tm.K)
    (actions : List (TransitionStmtStackAction tm)) :
    (transitionStmtStackActionsFor tm target actions).length =
      transitionStmtStackActionCountFor tm target actions := by
  induction actions with
  | nil => rfl
  | cons action rest ih =>
      change (List.filterMap
          (TransitionStmtStackAction.selectFor tm target) rest).length =
        transitionStmtStackActionCountFor tm target rest at ih
      simp only [TransitionStmtStackAction.selectFor] at ih
      rcases action with ⟨selected, kind⟩
      by_cases hselected : selected = target
      · subst selected
        cases kind <;>
          simp [transitionStmtStackActionsFor,
            TransitionStmtStackAction.selectFor,
            TransitionStmtStackAction.actionCountFor,
            transitionStmtStackActionCountFor, ih] <;> omega
      · cases kind <;>
          simp [transitionStmtStackActionsFor,
            TransitionStmtStackAction.selectFor,
            TransitionStmtStackAction.actionCountFor,
            transitionStmtStackActionCountFor, hselected, ih] <;> omega

/-- Counting one global action agrees with first selecting it for the target
stack and then counting the selected action. -/
theorem TransitionStmtStackAction.pushCountFor_eq_selectFor
    (tm : _root_.Turing.FinTM2) (target : tm.K)
    (action : TransitionStmtStackAction tm) :
    action.pushCountFor tm target =
      match action.selectFor tm target with
      | none => 0
      | some selected => selected.pushCount tm target := by
  rcases action with ⟨selected, kind⟩
  by_cases hselected : selected = target
  · subst selected
    cases kind <;>
      simp [TransitionStmtStackAction.pushCountFor,
        TransitionStmtStackAction.selectFor,
        TransitionStmtSelectedStackAction.pushCount]
  · cases kind <;>
      simp [TransitionStmtStackAction.pushCountFor,
        TransitionStmtStackAction.selectFor, hselected]

/-- Filtering a heterogeneous action table for one stack preserves exactly
the pushes aimed at that stack. -/
theorem transitionStmtStackActionsFor_pushCount_eq
    (tm : _root_.Turing.FinTM2) (target : tm.K)
    (actions : List (TransitionStmtStackAction tm)) :
    transitionStmtSelectedStackActionPushCount tm target
        (transitionStmtStackActionsFor tm target actions) =
      transitionStmtStackActionPushCountFor tm target actions := by
  induction actions with
  | nil => rfl
  | cons action rest ih =>
      change transitionStmtSelectedStackActionPushCount tm target
          (List.filterMap (TransitionStmtStackAction.selectFor tm target)
            (action :: rest)) = _
      change transitionStmtSelectedStackActionPushCount tm target
          (List.filterMap (TransitionStmtStackAction.selectFor tm target)
            rest) = _ at ih
      rw [List.filterMap_cons]
      rw [show transitionStmtStackActionPushCountFor tm target
          (action :: rest) =
            action.pushCountFor tm target +
              transitionStmtStackActionPushCountFor tm target rest by rfl]
      rw [action.pushCountFor_eq_selectFor tm target]
      cases hselected : action.selectFor tm target with
      | none => simp [ih]
      | some selected =>
          simp [transitionStmtSelectedStackActionPushCount, ih]

private theorem transitionStmtTerminalStackActionsFrom_pushCount_eq
    (tm : _root_.Turing.FinTM2) (target : tm.K) :
    ∀ (gateOffset : TransitionAffineNat)
      (q : _root_.Turing.TM2.Stmt tm.Γ tm.Λ tm.σ)
      (hsupport : ∀ k,
        stmtPushSet tm q k ⊆ reachableAlphabet tm k)
      (actions : List (TransitionStmtStackAction tm)),
      transitionStmtTerminalStackActionsFrom tm gateOffset q hsupport =
          some actions →
        transitionStmtStackActionPushCountFor tm target actions =
          stmtMaxPushes tm target q := by
  intro gateOffset q
  induction q generalizing gateOffset with
  | halt =>
      intro hsupport actions hactions
      simp [transitionStmtTerminalStackActionsFrom] at hactions
      subst actions
      rfl
  | goto jump =>
      intro hsupport actions hactions
      simp [transitionStmtTerminalStackActionsFrom] at hactions
      subst actions
      rfl
  | load update continuation ih =>
      intro hsupport actions hactions
      have hcontinuation :
          ∀ k, stmtPushSet tm continuation k ⊆ reachableAlphabet tm k := by
        simpa [stmtPushSet] using hsupport
      exact ih
        (gateOffset.add (TransitionAffineNat.const
          (stateCount tm + stateCount tm)))
        hcontinuation actions hactions
  | push selected emit continuation ih =>
      intro hsupport actions hactions
      have hcontinuation :
          ∀ k, stmtPushSet tm continuation k ⊆ reachableAlphabet tm k := by
        intro k symbol hsymbol
        apply hsupport k
        simp only [stmtPushSet]
        exact Finset.mem_union_right _ hsymbol
      let symbolAt : Fin (stateCount tm) → SupportedSymbol tm selected :=
        fun code =>
          ⟨emit ((stateEquivFin tm).symm code), by
            apply hsupport selected
            simp [stmtPushSet]⟩
      let action : TransitionStmtStackAction tm :=
        { k := selected
          kind := .push fun symbol =>
            gateOffset.add (TransitionAffineNat.const
              (oneHotMapWireOffset
                (fun code => encodeSupportedSymbol (symbolAt code)) symbol)) }
      change (transitionStmtTerminalStackActionsFrom tm
        (gateOffset.add (TransitionAffineNat.const
          (stateCount tm + (reachableAlphabet tm selected).card)))
        continuation hcontinuation).map (action :: ·) = some actions at hactions
      cases hrest : transitionStmtTerminalStackActionsFrom tm
          (gateOffset.add (TransitionAffineNat.const
            (stateCount tm + (reachableAlphabet tm selected).card)))
          continuation hcontinuation with
      | none => simp [hrest] at hactions
      | some rest =>
          rw [hrest] at hactions
          simp only [Option.map_some, Option.some.injEq] at hactions
          subst actions
          rw [show transitionStmtStackActionPushCountFor tm target
              (action :: rest) =
                (if selected = target then 1 else 0) +
                  transitionStmtStackActionPushCountFor tm target rest by
            simp [transitionStmtStackActionPushCountFor,
              TransitionStmtStackAction.pushCountFor, action]]
          rw [ih _ hcontinuation rest hrest]
          rfl
  | peek selected update continuation ih =>
      intro hsupport actions hactions
      have hcontinuation :
          ∀ k, stmtPushSet tm continuation k ⊆ reachableAlphabet tm k := by
        simpa [stmtPushSet] using hsupport
      exact ih
        (gateOffset.add (TransitionAffineNat.const
          (2 * stateCount tm *
            ((reachableAlphabet tm selected).card + 1) + stateCount tm)))
        hcontinuation actions hactions
  | pop selected update continuation ih =>
      intro hsupport actions hactions
      have hcontinuation :
          ∀ k, stmtPushSet tm continuation k ⊆ reachableAlphabet tm k := by
        simpa [stmtPushSet] using hsupport
      let action : TransitionStmtStackAction tm :=
        { k := selected
          kind := .pop gateOffset }
      change (transitionStmtTerminalStackActionsFrom tm
        (gateOffset.add (TransitionAffineNat.const
          (1 + 2 * stateCount tm *
            ((reachableAlphabet tm selected).card + 1) + stateCount tm)))
        continuation hcontinuation).map (action :: ·) = some actions at hactions
      cases hrest : transitionStmtTerminalStackActionsFrom tm
          (gateOffset.add (TransitionAffineNat.const
            (1 + 2 * stateCount tm *
              ((reachableAlphabet tm selected).card + 1) + stateCount tm)))
          continuation hcontinuation with
      | none => simp [hrest] at hactions
      | some rest =>
          rw [hrest] at hactions
          simp only [Option.map_some, Option.some.injEq] at hactions
          subst actions
          rw [show transitionStmtStackActionPushCountFor tm target
              (action :: rest) =
                transitionStmtStackActionPushCountFor tm target rest by
            simp [transitionStmtStackActionPushCountFor,
              TransitionStmtStackAction.pushCountFor, action]]
          exact ih _ hcontinuation rest hrest
  | branch test whenTrue whenFalse ihTrue ihFalse =>
      intro hsupport actions hactions
      simp [transitionStmtTerminalStackActionsFrom] at hactions

/-- The action table extracted from a terminal statement spine contains
exactly the pushes counted by the semantic statement bound. -/
theorem transitionStmtTerminalStackActions_pushCount_eq_stmtMaxPushes
    (tm : _root_.Turing.FinTM2) (target : tm.K)
    (q : _root_.Turing.TM2.Stmt tm.Γ tm.Λ tm.σ)
    (hsupport : ∀ k, stmtPushSet tm q k ⊆ reachableAlphabet tm k)
    (actions : List (TransitionStmtStackAction tm))
    (hactions : transitionStmtTerminalStackActions tm q hsupport =
      some actions) :
    transitionStmtStackActionPushCountFor tm target actions =
      stmtMaxPushes tm target q := by
  exact transitionStmtTerminalStackActionsFrom_pushCount_eq tm target
    (TransitionAffineNat.const 0) q hsupport actions hactions

private theorem transitionStmtTerminalStackActionsFrom_actionCount_eq
    (tm : _root_.Turing.FinTM2) (target : tm.K) :
    ∀ (gateOffset : TransitionAffineNat)
      (q : _root_.Turing.TM2.Stmt tm.Γ tm.Λ tm.σ)
      (hsupport : ∀ k,
        stmtPushSet tm q k ⊆ reachableAlphabet tm k)
      (actions : List (TransitionStmtStackAction tm)),
      transitionStmtTerminalStackActionsFrom tm gateOffset q hsupport =
          some actions →
        transitionStmtStackActionCountFor tm target actions =
          stmtMaxStackActions tm target q := by
  intro gateOffset q
  induction q generalizing gateOffset with
  | halt =>
      intro hsupport actions hactions
      simp [transitionStmtTerminalStackActionsFrom] at hactions
      subst actions
      rfl
  | goto jump =>
      intro hsupport actions hactions
      simp [transitionStmtTerminalStackActionsFrom] at hactions
      subst actions
      rfl
  | load update continuation ih =>
      intro hsupport actions hactions
      have hcontinuation :
          ∀ k, stmtPushSet tm continuation k ⊆ reachableAlphabet tm k := by
        simpa [stmtPushSet] using hsupport
      exact ih
        (gateOffset.add (TransitionAffineNat.const
          (stateCount tm + stateCount tm)))
        hcontinuation actions hactions
  | push selected emit continuation ih =>
      intro hsupport actions hactions
      have hcontinuation :
          ∀ k, stmtPushSet tm continuation k ⊆ reachableAlphabet tm k := by
        intro k symbol hsymbol
        apply hsupport k
        simp only [stmtPushSet]
        exact Finset.mem_union_right _ hsymbol
      let symbolAt : Fin (stateCount tm) → SupportedSymbol tm selected :=
        fun code =>
          ⟨emit ((stateEquivFin tm).symm code), by
            apply hsupport selected
            simp [stmtPushSet]⟩
      let action : TransitionStmtStackAction tm :=
        { k := selected
          kind := .push fun symbol =>
            gateOffset.add (TransitionAffineNat.const
              (oneHotMapWireOffset
                (fun code => encodeSupportedSymbol (symbolAt code)) symbol)) }
      change (transitionStmtTerminalStackActionsFrom tm
        (gateOffset.add (TransitionAffineNat.const
          (stateCount tm + (reachableAlphabet tm selected).card)))
        continuation hcontinuation).map (action :: ·) = some actions at hactions
      cases hrest : transitionStmtTerminalStackActionsFrom tm
          (gateOffset.add (TransitionAffineNat.const
            (stateCount tm + (reachableAlphabet tm selected).card)))
          continuation hcontinuation with
      | none => simp [hrest] at hactions
      | some rest =>
          rw [hrest] at hactions
          simp only [Option.map_some, Option.some.injEq] at hactions
          subst actions
          rw [show transitionStmtStackActionCountFor tm target
              (action :: rest) =
                (if selected = target then 1 else 0) +
                  transitionStmtStackActionCountFor tm target rest by
            simp [transitionStmtStackActionCountFor,
              TransitionStmtStackAction.actionCountFor, action]]
          rw [ih _ hcontinuation rest hrest]
          rfl
  | peek selected update continuation ih =>
      intro hsupport actions hactions
      have hcontinuation :
          ∀ k, stmtPushSet tm continuation k ⊆ reachableAlphabet tm k := by
        simpa [stmtPushSet] using hsupport
      exact ih
        (gateOffset.add (TransitionAffineNat.const
          (2 * stateCount tm *
            ((reachableAlphabet tm selected).card + 1) + stateCount tm)))
        hcontinuation actions hactions
  | pop selected update continuation ih =>
      intro hsupport actions hactions
      have hcontinuation :
          ∀ k, stmtPushSet tm continuation k ⊆ reachableAlphabet tm k := by
        simpa [stmtPushSet] using hsupport
      let action : TransitionStmtStackAction tm :=
        { k := selected
          kind := .pop gateOffset }
      change (transitionStmtTerminalStackActionsFrom tm
        (gateOffset.add (TransitionAffineNat.const
          (1 + 2 * stateCount tm *
            ((reachableAlphabet tm selected).card + 1) + stateCount tm)))
        continuation hcontinuation).map (action :: ·) = some actions at hactions
      cases hrest : transitionStmtTerminalStackActionsFrom tm
          (gateOffset.add (TransitionAffineNat.const
            (1 + 2 * stateCount tm *
              ((reachableAlphabet tm selected).card + 1) + stateCount tm)))
          continuation hcontinuation with
      | none => simp [hrest] at hactions
      | some rest =>
          rw [hrest] at hactions
          simp only [Option.map_some, Option.some.injEq] at hactions
          subst actions
          rw [show transitionStmtStackActionCountFor tm target
              (action :: rest) =
                (if selected = target then 1 else 0) +
                  transitionStmtStackActionCountFor tm target rest by
            simp [transitionStmtStackActionCountFor,
              TransitionStmtStackAction.actionCountFor, action]]
          rw [ih _ hcontinuation rest hrest]
          rfl
  | branch test whenTrue whenFalse ihTrue ihFalse =>
      intro hsupport actions hactions
      simp [transitionStmtTerminalStackActionsFrom] at hactions

/-- The terminal action table contains exactly as many commands for the
selected stack as the structural statement-path action measure. -/
theorem transitionStmtTerminalStackActions_length_eq_stmtMaxStackActions
    (tm : _root_.Turing.FinTM2) (target : tm.K)
    (q : _root_.Turing.TM2.Stmt tm.Γ tm.Λ tm.σ)
    (hsupport : ∀ k, stmtPushSet tm q k ⊆ reachableAlphabet tm k)
    (actions : List (TransitionStmtStackAction tm))
    (hactions : transitionStmtTerminalStackActions tm q hsupport =
      some actions) :
    (transitionStmtStackActionsFor tm target actions).length =
      stmtMaxStackActions tm target q := by
  rw [transitionStmtStackActionsFor_length_eq]
  exact transitionStmtTerminalStackActionsFrom_actionCount_eq tm target
    (TransitionAffineNat.const 0) q hsupport actions hactions

/-- A complete terminal row extracted from a machine label never contains
more selected-stack pushes than the uniform one-step machine bound. -/
theorem TransitionStmtTerminalRowLayout.selectedPushCount_le_maxPushesPerStep
    (tm : _root_.Turing.FinTM2) (label : tm.Λ)
    (hsupport : ∀ k,
      stmtPushSet tm (tm.m label) k ⊆ reachableAlphabet tm k)
    (layout : TransitionStmtTerminalRowLayout tm)
    (hlayout : transitionStmtTerminalRowLayout tm (tm.m label) hsupport =
      some layout) (target : tm.K) :
    transitionStmtSelectedStackActionPushCount tm target
        (transitionStmtStackActionsFor tm target layout.stackActions) ≤
      maxPushesPerStep tm := by
  unfold transitionStmtTerminalRowLayout at hlayout
  cases hterminal : transitionStmtTerminalLayout tm (tm.m label) with
  | none => simp [hterminal] at hlayout
  | some terminal =>
      cases hstate : transitionStmtTerminalStateLayout tm (tm.m label) with
      | none => simp [hterminal, hstate] at hlayout
      | some state =>
          cases hstack : transitionStmtTerminalStackActions tm (tm.m label)
              hsupport with
          | none => simp [hterminal, hstate, hstack] at hlayout
          | some actions =>
              simp [hterminal, hstate, hstack] at hlayout
              subst layout
              rw [transitionStmtStackActionsFor_pushCount_eq]
              rw [transitionStmtTerminalStackActions_pushCount_eq_stmtMaxPushes
                tm target (tm.m label) hsupport actions hstack]
              exact stmtMaxPushes_le_maxPushesPerStep tm label target

/-- A complete terminal row contains at most the uniform machine-static
number of selected-stack push/pop commands. -/
theorem TransitionStmtTerminalRowLayout.selectedActionCount_le_maxStackActionsPerStep
    (tm : _root_.Turing.FinTM2) (label : tm.Λ)
    (hsupport : ∀ k,
      stmtPushSet tm (tm.m label) k ⊆ reachableAlphabet tm k)
    (layout : TransitionStmtTerminalRowLayout tm)
    (hlayout : transitionStmtTerminalRowLayout tm (tm.m label) hsupport =
      some layout) (target : tm.K) :
    (transitionStmtStackActionsFor tm target layout.stackActions).length ≤
      maxStackActionsPerStep tm := by
  unfold transitionStmtTerminalRowLayout at hlayout
  cases hterminal : transitionStmtTerminalLayout tm (tm.m label) with
  | none => simp [hterminal] at hlayout
  | some terminal =>
      cases hstate : transitionStmtTerminalStateLayout tm (tm.m label) with
      | none => simp [hterminal, hstate] at hlayout
      | some state =>
          cases hstack : transitionStmtTerminalStackActions tm (tm.m label)
              hsupport with
          | none => simp [hterminal, hstate, hstack] at hlayout
          | some actions =>
              simp [hterminal, hstate, hstack] at hlayout
              subst layout
              rw [transitionStmtTerminalStackActions_length_eq_stmtMaxStackActions
                tm target (tm.m label) hsupport actions hstack]
              exact stmtMaxStackActions_le_maxStackActionsPerStep
                tm label target

/-- The widened one-step workspace has room for every push in a terminal row,
independently of the public tableau height. -/
theorem TransitionStmtTerminalRowLayout.selectedPushCount_le_workHeight
    (tm : _root_.Turing.FinTM2) (label : tm.Λ)
    (hsupport : ∀ k,
      stmtPushSet tm (tm.m label) k ⊆ reachableAlphabet tm k)
    (layout : TransitionStmtTerminalRowLayout tm)
    (hlayout : transitionStmtTerminalRowLayout tm (tm.m label) hsupport =
      some layout) (target : tm.K) (height : Nat) :
    transitionStmtSelectedStackActionPushCount tm target
        (transitionStmtStackActionsFor tm target layout.stackActions) ≤
      workHeight tm height := by
  exact le_trans
    (layout.selectedPushCount_le_maxPushesPerStep tm label hsupport hlayout
      target)
    (by simp [workHeight])

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