Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_8b09ad90ba63d5e871855a77

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

/-!
# End-to-end execution of the routed dispatch true-arm channel

The unified mux descriptor source stores one verifier-fixed prefix-drop amount
before every raw true-arm affine span.  The preceding modules physically
recover and execute those spans while retaining one boundary per span.  This
module cycles through the fixed drop table, removes the declared row prefixes,
and erases the temporary span boundaries.

The resulting byte stream is proved equal both to the established complete
true-arm compiler and to the actual semantic true inputs of every dispatch
mux.  Thus the routed true channel is closed end to end from the original
verifier word.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- Fixed prefix-drop period stored by one complete transition seed. -/
noncomputable def transitionDispatchTrueArmSpanDropAmounts
    (tm : _root_.Turing.FinTM2) : List Nat :=
  (transitionDispatchTrueArmNormalizedLayouts tm).flatMap
    (TransitionDispatchTrueArmNormalizedLayout.affineSpanDropAmounts tm)

private theorem
    TransitionDispatchTrueArmNormalizedLayout.affineSpanDropAmounts_nonempty
    (tm : _root_.Turing.FinTM2)
    (layout : TransitionDispatchTrueArmNormalizedLayout tm) :
    0 < (layout.affineSpanDropAmounts tm).length := by
  cases layout with
  | branch =>
      simp [TransitionDispatchTrueArmNormalizedLayout.affineSpanDropAmounts]
  | terminal labelOffset label rowLayout hlayout =>
      exact rowLayout.terminalAffineSpanDropAmounts_nonempty tm labelOffset

private theorem transitionDispatchTrueArmNormalizedLayouts_nonempty
    (tm : _root_.Turing.FinTM2) :
    transitionDispatchTrueArmNormalizedLayouts tm ≠ [] := by
  unfold transitionDispatchTrueArmNormalizedLayouts
  cases hlabels : programLabels tm with
  | nil => exact False.elim (programLabels_nonempty tm hlabels)
  | cons label labels =>
      simp only [transitionDispatchTrueArmNormalizedLayoutsForLabels]
      split <;> simp

/-- The fixed drop period is nonempty because the verifier program has at
least one label and every normalized label contributes at least one span. -/
theorem transitionDispatchTrueArmSpanDropAmounts_nonempty
    (tm : _root_.Turing.FinTM2) :
    0 < (transitionDispatchTrueArmSpanDropAmounts tm).length := by
  obtain ⟨layout, layouts, hlayouts⟩ := List.exists_cons_of_ne_nil
    (transitionDispatchTrueArmNormalizedLayouts_nonempty tm)
  unfold transitionDispatchTrueArmSpanDropAmounts
  rw [hlayouts]
  simp only [List.flatMap_cons, List.length_append]
  have hhead := layout.affineSpanDropAmounts_nonempty tm
  omega

private theorem transitionDispatchTrueArmSpanRawProgressionsFrom_length
    (seed : TransitionRowSeed) :
    ∀ (amounts : List Nat)
      (segments : List TransitionWidenedFallbackSegment),
      amounts.length = segments.length →
      (transitionDispatchTrueArmSpanRawProgressionsFrom seed amounts
        segments).length = amounts.length := by
  intro amounts
  induction amounts with
  | nil =>
      intro segments hlength
      have hnil : segments = [] := List.eq_nil_of_length_eq_zero hlength.symm
      subst segments
      rfl
  | cons amount amounts ih =>
      intro segments hlength
      cases segments with
      | nil => simp at hlength
      | cons segment segments =>
          simp only [List.length_cons] at hlength
          simp only [transitionDispatchTrueArmSpanRawProgressionsFrom,
            List.length_cons]
          rw [ih segments (by omega)]

/-- Every executed span-row period has exactly the length of the fixed drop
table that accompanies it. -/
theorem transitionDispatchTrueArmSpanRawValueRows_length
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    (transitionDispatchTrueArmSpanRawValueRows tm seed).length =
      (transitionDispatchTrueArmSpanDropAmounts tm).length := by
  unfold transitionDispatchTrueArmSpanRawValueRows
    transitionDispatchTrueArmSpanRawProgressions
    transitionDispatchTrueArmSpanDropAmounts
  rw [List.length_map]
  induction transitionDispatchTrueArmNormalizedLayouts tm with
  | nil => rfl
  | cons layout layouts ih =>
      simp only [List.flatMap_cons, List.length_append]
      rw [transitionDispatchTrueArmSpanRawProgressionsFrom_length seed
        (layout.affineSpanDropAmounts tm) (layout.affineSpanSegments tm)
        (layout.affineSpanDropAmounts_length tm), ih]

private theorem unaryFramePeriodicPrefixDropValues_append
    (leftDrops rightDrops : List Nat)
    (leftRows rightRows : List (List Nat))
    (hlength : leftDrops.length = leftRows.length) :
    unaryFramePeriodicPrefixDropValues (leftDrops ++ rightDrops)
        (leftRows ++ rightRows) =
      unaryFramePeriodicPrefixDropValues leftDrops leftRows ++
        unaryFramePeriodicPrefixDropValues rightDrops rightRows := by
  induction leftDrops generalizing leftRows with
  | nil =>
      have hnil : leftRows = [] := List.eq_nil_of_length_eq_zero hlength.symm
      subst leftRows
      rfl
  | cons amount amounts ih =>
      cases leftRows with
      | nil => simp at hlength
      | cons row rows =>
          simp only [List.length_cons] at hlength
          simp only [List.cons_append,
            unaryFramePeriodicPrefixDropValues]
          rw [ih rows (by omega)]

private theorem transitionDispatchTrueArmSpanDroppedValueRowsFrom
    (seed : TransitionRowSeed) :
    ∀ (amounts : List Nat)
      (segments : List TransitionWidenedFallbackSegment),
      unaryFramePeriodicPrefixDropValues amounts
          ((transitionDispatchTrueArmSpanRawProgressionsFrom seed amounts
            segments).map transitionProgressionFirstValues) =
        (transitionDispatchTrueArmSpanProgressionsFrom seed amounts
          segments).map transitionProgressionFirstValues := by
  intro amounts
  induction amounts with
  | nil =>
      intro segments
      rfl
  | cons amount amounts ih =>
      intro segments
      cases segments with
      | nil => rfl
      | cons segment segments =>
          simp only [transitionDispatchTrueArmSpanRawProgressionsFrom,
            transitionDispatchTrueArmSpanProgressionsFrom, List.map_cons,
            unaryFramePeriodicPrefixDropValues]
          rw [ih]
          rw [show transitionProgressionFirstValues
              (transitionWidenedFallbackSegmentProgression seed segment) =
                transitionWidenedFallbackSegmentValues seed segment by rfl]
          rw [transitionDispatchTrueArmSpanProgression_firstValues]

private theorem list_flatten_append {α : Type}
    (left right : List (List α)) :
    (left ++ right).flatten = left.flatten ++ right.flatten := by
  induction left with
  | nil => rfl
  | cons head tail ih =>
      simp only [List.cons_append, List.flatten_cons, ih,
        List.append_assoc]

private theorem list_flatten_map_eq_flatMap {α β : Type}
    (values : List α) (f : α → List β) :
    (values.map f).flatten = values.flatMap f := by
  induction values with
  | nil => rfl
  | cons value values ih =>
      simp only [List.map_cons, List.flatten_cons, List.flatMap_cons, ih]

private theorem flattenedProgressionGroups_firstValues
    (groups : List (List AffineUnaryTripleProgression)) :
    ((groups.flatten.map transitionProgressionFirstValues).flatten) =
      (groups.map fun progressions =>
        progressions.flatMap transitionProgressionFirstValues).flatten := by
  induction groups with
  | nil => rfl
  | cons group groups ih =>
      simp only [List.flatten_cons, List.map_append, List.map_cons]
      rw [list_flatten_append]
      rw [list_flatten_map_eq_flatMap]
      rw [ih]

/-- Semantic value rows after applying the fixed drop table to one executed
raw span period. -/
noncomputable def transitionDispatchTrueArmSpanDroppedValueRows
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    List (List Nat) :=
  unaryFramePeriodicPrefixDropValues
    (transitionDispatchTrueArmSpanDropAmounts tm)
    (transitionDispatchTrueArmSpanRawValueRows tm seed)

/-- Periodic physical prefix deletion is exactly descriptor-level
normalization of every true-arm span. -/
theorem transitionDispatchTrueArmSpanDroppedValueRows_eq
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    transitionDispatchTrueArmSpanDroppedValueRows tm seed =
      (transitionDispatchTrueArmSpanProgressionGroups tm seed).flatten.map
        transitionProgressionFirstValues := by
  unfold transitionDispatchTrueArmSpanDroppedValueRows
    transitionDispatchTrueArmSpanDropAmounts
    transitionDispatchTrueArmSpanRawValueRows
    transitionDispatchTrueArmSpanRawProgressions
    transitionDispatchTrueArmSpanProgressionGroups
    TransitionDispatchTrueArmNormalizedLayout.affineSpanProgressions
  rw [List.map_flatMap]
  induction transitionDispatchTrueArmNormalizedLayouts tm with
  | nil => rfl
  | cons layout layouts ih =>
      simp only [List.flatMap_cons, List.map_cons, List.flatten_cons,
        List.map_append]
      rw [unaryFramePeriodicPrefixDropValues_append]
      · rw [transitionDispatchTrueArmSpanDroppedValueRowsFrom, ih]
      · rw [List.length_map]
        exact (transitionDispatchTrueArmSpanRawProgressionsFrom_length seed
          (layout.affineSpanDropAmounts tm)
          (layout.affineSpanSegments tm)
          (layout.affineSpanDropAmounts_length tm)).symm

/-- Apply the fixed drop period while preserving every temporary span
boundary. -/
noncomputable def
    verifierTransitionDispatchMuxInvocationDescriptorTrueDroppedSpanMarkedFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List UnaryFrameSym :=
  rewriteUnaryFramePeriodicPrefixDrop
    (transitionDispatchTrueArmSpanDropAmounts W.machine.tm)
    (transitionDispatchTrueArmSpanDropAmounts_nonempty W.machine.tm)
    (verifierTransitionDispatchMuxInvocationDescriptorTrueRawMarkedFrames
      W input)

/-- Exact marked-row semantics after the periodic prefix-drop pass. -/
theorem
    verifierTransitionDispatchMuxInvocationDescriptorTrueDroppedSpanMarkedFrames_eq
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierTransitionDispatchMuxInvocationDescriptorTrueDroppedSpanMarkedFrames
        W input =
      encodeUnaryFramePeriodicPrefixDropOutput
        (transitionDispatchTrueArmSpanDropAmounts W.machine.tm)
        (verifierTransitionDispatchMuxInvocationDescriptorTrueRawValueRowGroups
          W input) := by
  unfold
    verifierTransitionDispatchMuxInvocationDescriptorTrueDroppedSpanMarkedFrames
  rw [verifierTransitionDispatchMuxInvocationDescriptorTrueRawMarkedFrames_eq]
  apply rewriteUnaryFramePeriodicPrefixDrop_groups
  intro group hgroup
  unfold
    verifierTransitionDispatchMuxInvocationDescriptorTrueRawValueRowGroups at hgroup
  rw [List.mem_map] at hgroup
  rcases hgroup with ⟨seed, hseed, rfl⟩
  exact transitionDispatchTrueArmSpanRawValueRows_length W.machine.tm seed

/-- Erase temporary span boundaries after every declared prefix has been
removed. -/
noncomputable def
    verifierTransitionDispatchMuxInvocationDescriptorTrueValueFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List UnaryFrameSym :=
  unmarkAffineUnaryTripleProgressionRows
    (verifierTransitionDispatchMuxInvocationDescriptorTrueDroppedSpanMarkedFrames
      W input)

/-- The routed true channel evaluates to the actual semantic true inputs of
every dispatch mux. -/
theorem
    verifierTransitionDispatchMuxInvocationDescriptorTrueValueFrames_eq_semantic
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierTransitionDispatchMuxInvocationDescriptorTrueValueFrames W input =
      encodeUnaryFrame
        ((verifierTransitionRowSeeds W input).flatMap fun seed =>
          (transitionDispatchTrueArmRowsFromSeed W.machine.tm seed).flatten) := by
  unfold verifierTransitionDispatchMuxInvocationDescriptorTrueValueFrames
  rw [verifierTransitionDispatchMuxInvocationDescriptorTrueDroppedSpanMarkedFrames_eq]
  rw [show
      encodeUnaryFramePeriodicPrefixDropOutput
          (transitionDispatchTrueArmSpanDropAmounts W.machine.tm)
          (verifierTransitionDispatchMuxInvocationDescriptorTrueRawValueRowGroups
            W input) =
        ((verifierTransitionRowSeeds W input).flatMap fun seed =>
          transitionDispatchTrueArmSpanDroppedValueRows W.machine.tm seed).flatMap
            (fun row => encodeUnaryFrame row ++ [.frameEnd]) by
      unfold encodeUnaryFramePeriodicPrefixDropOutput
        verifierTransitionDispatchMuxInvocationDescriptorTrueRawValueRowGroups
        transitionDispatchTrueArmSpanDroppedValueRows
      simp [List.flatMap_map, List.flatMap_assoc]]
  rw [unmarkAffineUnaryTripleProgressionRows_markedValues]
  congr 1
  rw [List.flatten_eq_flatMap, List.flatMap_assoc]
  apply List.flatMap_congr
  intro seed hseed
  rw [transitionDispatchTrueArmSpanDroppedValueRows_eq]
  have hsemantic := transitionDispatchTrueArmSpanProgressionGroups_eq_seed
    W input seed hseed
  have hflatten := congrArg List.flatten hsemantic
  rw [← List.flatten_eq_flatMap]
  rw [flattenedProgressionGroups_firstValues]
  exact hflatten

/-- The routed execution is byte-for-byte the established complete true-arm
compiler. -/
theorem verifierTransitionDispatchMuxInvocationDescriptorTrueValueFrames_eq
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierTransitionDispatchMuxInvocationDescriptorTrueValueFrames W input =
      verifierTransitionDispatchTrueArmAffineSpanFrames W input := by
  rw [verifierTransitionDispatchMuxInvocationDescriptorTrueValueFrames_eq_semantic,
    verifierTransitionDispatchTrueArmAffineSpanFrames_eq_semantic]

/-- Periodic prefix deletion is polynomial-time from the original verifier
word. -/
noncomputable def
    verifierTransitionDispatchMuxInvocationDescriptorTrueDroppedSpanMarkedFrames_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierTransitionDispatchMuxInvocationDescriptorTrueDroppedSpanMarkedFrames
        W) := by
  let composed :=
    _root_.Turing.TM2Comp.TM2ComputableInPolyTime.comp_scratch
      (verifierTransitionDispatchMuxInvocationDescriptorTrueRawMarkedFrames_computableInPolyTime
        W)
      (unaryFramePeriodicPrefixDrop_computableInPolyTime
        (transitionDispatchTrueArmSpanDropAmounts W.machine.tm)
        (transitionDispatchTrueArmSpanDropAmounts_nonempty W.machine.tm))
  change _root_.Turing.TM2ComputableInPolyTime id id
    (fun input => rewriteUnaryFramePeriodicPrefixDrop
      (transitionDispatchTrueArmSpanDropAmounts W.machine.tm)
      (transitionDispatchTrueArmSpanDropAmounts_nonempty W.machine.tm)
      (verifierTransitionDispatchMuxInvocationDescriptorTrueRawMarkedFrames
        W input))
  simpa [Function.comp_def,
    verifierTransitionDispatchMuxInvocationDescriptorTrueDroppedSpanMarkedFrames]
    using Classical.choice composed

/-- The complete physical true-channel interpreter is one concrete
polynomial-time TM2 from the original verifier word. -/
noncomputable def
    verifierTransitionDispatchMuxInvocationDescriptorTrueValueFrames_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierTransitionDispatchMuxInvocationDescriptorTrueValueFrames W) := by
  let composed :=
    _root_.Turing.TM2Comp.TM2ComputableInPolyTime.comp_scratch
      (verifierTransitionDispatchMuxInvocationDescriptorTrueDroppedSpanMarkedFrames_computableInPolyTime
        W)
      unmarkAffineUnaryTripleProgressionRows_computableInPolyTime
  change _root_.Turing.TM2ComputableInPolyTime id id
    (fun input => unmarkAffineUnaryTripleProgressionRows
      (verifierTransitionDispatchMuxInvocationDescriptorTrueDroppedSpanMarkedFrames
        W input))
  simpa [Function.comp_def,
    verifierTransitionDispatchMuxInvocationDescriptorTrueValueFrames]
    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