Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_8996568dc69cf238a811b660

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_5775e18fdc27cf0f44f80a7d
import Definitions.Def_PricingWithTips3DM_8f5a0e5f7c4d0ac6c65b2125
import Definitions.Def_PricingWithTips3DM_4782b9fdf42b88b34f570564
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Exact stack-route descriptor selection semantics

The machine-fixed height and cell masks are identified with the corresponding
semantic progression families.  Consequently the concrete raw-input selector
emits exactly those marked descriptor families for every transition seed.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

private theorem flatMap_if_eq_nil_of_not_mem {ι α : Type}
    [DecidableEq ι] (target : ι) (values : List α)
    (indices : List ι) (hnot : target ∉ indices) :
    indices.flatMap (fun index => if index = target then values else []) =
      [] := by
  induction indices with
  | nil => rfl
  | cons index indices ih =>
      have hne : index ≠ target := by
        intro heq
        apply hnot
        simp [heq]
      have htail : target ∉ indices := by
        intro hmem
        exact hnot (by simp [hmem])
      simp [hne, ih htail]

private theorem flatMap_if_eq_of_mem_nodup {ι α : Type}
    [DecidableEq ι] (target : ι) (values : List α)
    (indices : List ι) (hmem : target ∈ indices)
    (hnodup : indices.Nodup) :
    indices.flatMap (fun index => if index = target then values else []) =
      values := by
  induction indices with
  | nil => simp at hmem
  | cons index indices ih =>
      rw [List.nodup_cons] at hnodup
      by_cases heq : index = target
      · subst index
        rw [List.flatMap_cons, if_pos rfl,
          flatMap_if_eq_nil_of_not_mem target values indices hnodup.1]
        simp
      · have htail : target ∈ indices := by
          simpa [heq, Ne.symm heq] using hmem
        rw [List.flatMap_cons, if_neg heq, ih htail hnodup.2]
        rfl

private theorem select_heightStackBlock
    (tm : _root_.Turing.FinTM2) (k : tm.K) :
    selectListByBool
        ([true, true] ++
          List.replicate (1 + 2 * maxPushesPerStep tm) false)
        (transitionWidenedFallbackStackSegments tm k) =
      transitionStackRouteHeightSegments tm k := by
  unfold transitionWidenedFallbackStackSegments
    transitionStackRouteHeightSegments
  rw [show
      [transitionWidenedFallbackPublicHeightSegment tm k,
          transitionWidenedFallbackOverflowHeightSegment tm,
          transitionWidenedFallbackPublicCellSegment tm k] ++
          (List.replicate (maxPushesPerStep tm)
            (transitionWidenedFallbackBlankCellSegments tm k)).flatten =
        [transitionWidenedFallbackPublicHeightSegment tm k,
          transitionWidenedFallbackOverflowHeightSegment tm] ++
          (transitionWidenedFallbackPublicCellSegment tm k ::
            (List.replicate (maxPushesPerStep tm)
              (transitionWidenedFallbackBlankCellSegments tm k)).flatten) by
      rfl]
  rw [selectListByBool_append]
  · simp [selectListByBool]
  · simp

private theorem select_cellStackBlock
    (tm : _root_.Turing.FinTM2) (k : tm.K) :
    selectListByBool
        ([false, false] ++
          List.replicate (1 + 2 * maxPushesPerStep tm) true)
        (transitionWidenedFallbackStackSegments tm k) =
      transitionStackRouteCellSegments tm k := by
  unfold transitionWidenedFallbackStackSegments
    transitionStackRouteCellSegments
  rw [show
      [transitionWidenedFallbackPublicHeightSegment tm k,
          transitionWidenedFallbackOverflowHeightSegment tm,
          transitionWidenedFallbackPublicCellSegment tm k] ++
          (List.replicate (maxPushesPerStep tm)
            (transitionWidenedFallbackBlankCellSegments tm k)).flatten =
        [transitionWidenedFallbackPublicHeightSegment tm k,
          transitionWidenedFallbackOverflowHeightSegment tm] ++
          (transitionWidenedFallbackPublicCellSegment tm k ::
            (List.replicate (maxPushesPerStep tm)
              (transitionWidenedFallbackBlankCellSegments tm k)).flatten) by
      rfl]
  rw [selectListByBool_append]
  · simp only [selectListByBool,
      selectListByBool_replicate_true]
    apply List.take_of_length_le
    simp [transitionWidenedFallbackBlankCellSegments]
    omega
  · simp

private theorem heightSelection_stackSegments
    (tm : _root_.Turing.FinTM2) (k : tm.K) :
    selectListByBool
        (transitionStackRouteHeightDescriptorSelection tm k)
        (transitionWidenedFallbackSegments tm) =
      transitionStackRouteHeightSegments tm k := by
  unfold transitionStackRouteHeightDescriptorSelection
    transitionWidenedFallbackSegments
  change selectListByBool
      ((arithmeticRuntimeStackSourceIndices tm).flatMap fun position =>
        if position = arithmeticStackEquiv tm k then
          [true, true] ++
            List.replicate (1 + 2 * maxPushesPerStep tm) false
        else
          List.replicate
            (transitionWidenedFallbackStackSegmentCount tm) false)
      ((arithmeticRuntimeStackSourceIndices tm).flatMap fun position =>
        transitionWidenedFallbackStackSegments tm
          ((arithmeticStackEquiv tm).symm position)) =
    transitionStackRouteHeightSegments tm k
  have hlength : ∀ position ∈ arithmeticRuntimeStackSourceIndices tm,
      (if position = arithmeticStackEquiv tm k then
          [true, true] ++
            List.replicate (1 + 2 * maxPushesPerStep tm) false
        else
          List.replicate
            (transitionWidenedFallbackStackSegmentCount tm) false).length =
        (transitionWidenedFallbackStackSegments tm
          ((arithmeticStackEquiv tm).symm position)).length := by
    intro position hposition
    rw [transitionWidenedFallbackStackSegments_length]
    by_cases htarget : position = arithmeticStackEquiv tm k
    · simp [htarget, transitionWidenedFallbackStackSegmentCount]
      omega
    · simp [htarget]
  rw [selectListByBool_flatMap _ _ _ hlength]
  have hlocal :
      (arithmeticRuntimeStackSourceIndices tm).flatMap (fun position =>
        selectListByBool
          (if position = arithmeticStackEquiv tm k then
            [true, true] ++
              List.replicate (1 + 2 * maxPushesPerStep tm) false
          else
            List.replicate
              (transitionWidenedFallbackStackSegmentCount tm) false)
          (transitionWidenedFallbackStackSegments tm
            ((arithmeticStackEquiv tm).symm position))) =
        (arithmeticRuntimeStackSourceIndices tm).flatMap (fun position =>
          if position = arithmeticStackEquiv tm k then
            transitionStackRouteHeightSegments tm k
          else []) := by
    apply List.flatMap_congr
    intro position hposition
    by_cases htarget : position = arithmeticStackEquiv tm k
    · simp only [if_pos htarget]
      subst position
      simpa only [Equiv.symm_apply_apply, List.cons_append,
        List.nil_append] using
        select_heightStackBlock tm k
    · simp [htarget]
  rw [hlocal]
  apply flatMap_if_eq_of_mem_nodup
      (arithmeticStackEquiv tm k)
      (transitionStackRouteHeightSegments tm k)
  · simp [arithmeticRuntimeStackSourceIndices]
  · exact List.nodup_finRange _

private theorem cellSelection_stackSegments
    (tm : _root_.Turing.FinTM2) (k : tm.K) :
    selectListByBool
        (transitionStackRouteCellDescriptorSelection tm k)
        (transitionWidenedFallbackSegments tm) =
      transitionStackRouteCellSegments tm k := by
  unfold transitionStackRouteCellDescriptorSelection
    transitionWidenedFallbackSegments
  change selectListByBool
      ((arithmeticRuntimeStackSourceIndices tm).flatMap fun position =>
        if position = arithmeticStackEquiv tm k then
          [false, false] ++
            List.replicate (1 + 2 * maxPushesPerStep tm) true
        else
          List.replicate
            (transitionWidenedFallbackStackSegmentCount tm) false)
      ((arithmeticRuntimeStackSourceIndices tm).flatMap fun position =>
        transitionWidenedFallbackStackSegments tm
          ((arithmeticStackEquiv tm).symm position)) =
    transitionStackRouteCellSegments tm k
  have hlength : ∀ position ∈ arithmeticRuntimeStackSourceIndices tm,
      (if position = arithmeticStackEquiv tm k then
          [false, false] ++
            List.replicate (1 + 2 * maxPushesPerStep tm) true
        else
          List.replicate
            (transitionWidenedFallbackStackSegmentCount tm) false).length =
        (transitionWidenedFallbackStackSegments tm
          ((arithmeticStackEquiv tm).symm position)).length := by
    intro position hposition
    rw [transitionWidenedFallbackStackSegments_length]
    by_cases htarget : position = arithmeticStackEquiv tm k
    · simp [htarget, transitionWidenedFallbackStackSegmentCount]
      omega
    · simp [htarget]
  rw [selectListByBool_flatMap _ _ _ hlength]
  have hlocal :
      (arithmeticRuntimeStackSourceIndices tm).flatMap (fun position =>
        selectListByBool
          (if position = arithmeticStackEquiv tm k then
            [false, false] ++
              List.replicate (1 + 2 * maxPushesPerStep tm) true
          else
            List.replicate
              (transitionWidenedFallbackStackSegmentCount tm) false)
          (transitionWidenedFallbackStackSegments tm
            ((arithmeticStackEquiv tm).symm position))) =
        (arithmeticRuntimeStackSourceIndices tm).flatMap (fun position =>
          if position = arithmeticStackEquiv tm k then
            transitionStackRouteCellSegments tm k
          else []) := by
    apply List.flatMap_congr
    intro position hposition
    by_cases htarget : position = arithmeticStackEquiv tm k
    · simp only [if_pos htarget]
      subst position
      simpa only [Equiv.symm_apply_apply, List.cons_append,
        List.nil_append] using
        select_cellStackBlock tm k
    · simp [htarget]
  rw [hlocal]
  apply flatMap_if_eq_of_mem_nodup
      (arithmeticStackEquiv tm k)
      (transitionStackRouteCellSegments tm k)
  · simp [arithmeticRuntimeStackSourceIndices]
  · exact List.nodup_finRange _

/-- The height mask selects exactly the two height progressions of one stack. -/
theorem transitionStackRouteHeightDescriptorSelection_progressions
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) (k : tm.K) :
    selectListByBool
        (transitionStackRouteHeightDescriptorSelection tm k)
        (transitionWidenedFallbackProgressions tm seed) =
      transitionStackRouteHeightProgressions tm seed k := by
  unfold transitionWidenedFallbackProgressions
    transitionStackRouteHeightProgressions
  rw [selectListByBool_map, heightSelection_stackSegments]

/-- The cell mask selects exactly the public-cell and blank-cell progressions
of one stack. -/
theorem transitionStackRouteCellDescriptorSelection_progressions
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) (k : tm.K) :
    selectListByBool
        (transitionStackRouteCellDescriptorSelection tm k)
        (transitionWidenedFallbackProgressions tm seed) =
      transitionStackRouteCellProgressions tm seed k := by
  unfold transitionWidenedFallbackProgressions
    transitionStackRouteCellProgressions
  rw [selectListByBool_map, cellSelection_stackSegments]

/-- From the raw verifier input, the height selector emits exactly the marked
height progression family for every transition seed. -/
theorem
    verifierTransitionStackRouteHeightMarkedDescriptorFrames_eq_routeProgressions
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (k : W.machine.tm.K) (input : List Γ) :
    verifierTransitionStackRouteHeightMarkedDescriptorFrames W k input =
      (verifierTransitionRowSeeds W input).flatMap fun seed =>
        encodeAffineUnaryTripleProgressionMarkedFamily
          (transitionStackRouteHeightProgressions W.machine.tm seed k) := by
  rw [verifierTransitionStackRouteHeightMarkedDescriptorFrames_eq_groups]
  unfold verifierTransitionWidenedFallbackDescriptorRowGroups
  rw [List.flatMap_map]
  apply List.flatMap_congr
  intro seed hseed
  rw [encodeUnaryFramePeriodicSelectedMarkedProgressions]
  rw [transitionStackRouteHeightDescriptorSelection_progressions]

/-- From the raw verifier input, the cell selector emits exactly the marked
cell progression family for every transition seed. -/
theorem
    verifierTransitionStackRouteCellMarkedDescriptorFrames_eq_routeProgressions
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (k : W.machine.tm.K) (input : List Γ) :
    verifierTransitionStackRouteCellMarkedDescriptorFrames W k input =
      (verifierTransitionRowSeeds W input).flatMap fun seed =>
        encodeAffineUnaryTripleProgressionMarkedFamily
          (transitionStackRouteCellProgressions W.machine.tm seed k) := by
  rw [verifierTransitionStackRouteCellMarkedDescriptorFrames_eq_groups]
  unfold verifierTransitionWidenedFallbackDescriptorRowGroups
  rw [List.flatMap_map]
  apply List.flatMap_congr
  intro seed hseed
  rw [encodeUnaryFramePeriodicSelectedMarkedProgressions]
  rw [transitionStackRouteCellDescriptorSelection_progressions]

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