Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_0a2139be1262bce20289f938

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

/-!
# Concrete prefix-deletion passes for stack-pop routes

A pop removes the first two height values and the first fixed-width cell row.
This module packages the two marked source streams, applies the reusable fixed
prefix controller, and identifies the result with the descriptor-level routes
already proved correct.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- One marked widened height row per transition seed. -/
noncomputable def transitionStackRouteHeightSourceFrames
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (seeds : List TransitionRowSeed) : List UnaryFrameSym :=
  encodeUnaryFrameFixedPrefixDropInput
    (seeds.map fun seed =>
      transitionStackRouteFirstValues
        (transitionStackRouteHeightProgressions tm seed k))

/-- Concrete controller output after deleting the two height values consumed
by pop. -/
noncomputable def transitionStackRoutePopHeightSliceFrames
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (seeds : List TransitionRowSeed) : List UnaryFrameSym :=
  rewriteUnaryFrameFixedPrefixDrop 2
    (transitionStackRouteHeightSourceFrames tm k seeds)

/-- The controller output is exactly the carried descriptor-family drop for
every seed. -/
theorem transitionStackRoutePopHeightSliceFrames_eq
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (seeds : List TransitionRowSeed) :
    transitionStackRoutePopHeightSliceFrames tm k seeds =
      encodeUnaryFrameFixedPrefixDropInput
        (seeds.map fun seed =>
          transitionStackRouteFirstValues
            (transitionStackRouteDropFamily 2
              (transitionStackRouteHeightProgressions tm seed k))) := by
  unfold transitionStackRoutePopHeightSliceFrames
    transitionStackRouteHeightSourceFrames
  rw [rewriteUnaryFrameFixedPrefixDrop_rows]
  unfold encodeUnaryFrameFixedPrefixDropOutput
    encodeUnaryFrameFixedPrefixDropInput
  rw [List.flatMap_map, List.flatMap_map]
  apply List.flatMap_congr
  intro seed hseed
  congr 2
  rw [transitionStackRouteHeightDrop_values]
  rw [← transitionStackRouteHeightProgressions_values]

/-- One marked flattened widened-cell row per transition seed. -/
noncomputable def transitionStackRouteCellSourceFrames
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (seeds : List TransitionRowSeed) : List UnaryFrameSym :=
  encodeUnaryFrameFixedPrefixDropInput
    (seeds.map fun seed =>
      transitionStackRouteFirstValues
        (transitionStackRouteCellProgressions tm seed k))

/-- Concrete controller output after deleting the old top cell row. -/
noncomputable def transitionStackRoutePopCellSliceFrames
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (seeds : List TransitionRowSeed) : List UnaryFrameSym :=
  rewriteUnaryFrameFixedPrefixDrop
    ((reachableAlphabet tm k).card + 1)
    (transitionStackRouteCellSourceFrames tm k seeds)

/-- The cell controller output is exactly the carried descriptor-family drop
by one machine-fixed symbol-row width. -/
theorem transitionStackRoutePopCellSliceFrames_eq
    (tm : _root_.Turing.FinTM2) (k : tm.K)
    (seeds : List TransitionRowSeed) :
    transitionStackRoutePopCellSliceFrames tm k seeds =
      encodeUnaryFrameFixedPrefixDropInput
        (seeds.map fun seed =>
          transitionStackRouteFirstValues
            (transitionStackRouteDropFamily
              ((reachableAlphabet tm k).card + 1)
              (transitionStackRouteCellProgressions tm seed k))) := by
  unfold transitionStackRoutePopCellSliceFrames
    transitionStackRouteCellSourceFrames
  rw [rewriteUnaryFrameFixedPrefixDrop_rows]
  unfold encodeUnaryFrameFixedPrefixDropOutput
    encodeUnaryFrameFixedPrefixDropInput
  rw [List.flatMap_map, List.flatMap_map]
  apply List.flatMap_congr
  intro seed hseed
  congr 2
  unfold transitionStackRouteFirstValues
  rw [transitionStackRouteDropFamily_rows, List.map_drop]

/-- Any polynomial-time marked height source is closed under the concrete pop
slice controller. -/
noncomputable def
    transitionStackRoutePopHeightSliceFrames_computableInPolyTime_of_source
    {Γ : Type} (tm : _root_.Turing.FinTM2) (k : tm.K)
    (seeds : List Γ → List TransitionRowSeed)
    (source : _root_.Turing.TM2ComputableInPolyTime id id
      (fun input => transitionStackRouteHeightSourceFrames tm k
        (seeds input))) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (fun input => transitionStackRoutePopHeightSliceFrames tm k
        (seeds input)) := by
  let composed :=
    _root_.Turing.TM2Comp.TM2ComputableInPolyTime.comp_scratch source
      (unaryFrameFixedPrefixDrop_computableInPolyTime 2)
  simpa [Function.comp_def, transitionStackRoutePopHeightSliceFrames] using
    Classical.choice composed

/-- Any polynomial-time marked cell source is closed under deletion of one
fixed-width top cell row. -/
noncomputable def
    transitionStackRoutePopCellSliceFrames_computableInPolyTime_of_source
    {Γ : Type} (tm : _root_.Turing.FinTM2) (k : tm.K)
    (seeds : List Γ → List TransitionRowSeed)
    (source : _root_.Turing.TM2ComputableInPolyTime id id
      (fun input => transitionStackRouteCellSourceFrames tm k
        (seeds input))) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (fun input => transitionStackRoutePopCellSliceFrames tm k
        (seeds input)) := by
  let composed :=
    _root_.Turing.TM2Comp.TM2ComputableInPolyTime.comp_scratch source
      (unaryFrameFixedPrefixDrop_computableInPolyTime
        ((reachableAlphabet tm k).card + 1))
  simpa [Function.comp_def, transitionStackRoutePopCellSliceFrames] using
    Classical.choice composed

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