Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_4cd655ad6f5d3d5353ce8e98

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

/-!
# Executed dispatch-mux fresh-coordinate source

This final thin layer runs the generated progression descriptors and identifies
their output with the semantic whole-row mux layouts.  It is kept separate so
changes to the recursive statement compiler do not force recompilation of the
generic affine source proofs.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- Repackage one emitted coordinate triple as a generic affine seed. -/
def transitionDispatchMuxCoordinateSeed
    (row : Nat × Nat × Nat) : AffineUnaryTripleSeed :=
  { first := row.1, second := row.2.1, third := row.2.2 }

/-- All fresh mux coordinate triples for one transition row. -/
def transitionDispatchMuxCoordinateSeeds
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    List AffineUnaryTripleSeed :=
  (transitionDispatchMuxAffineProgressions tm seed).flatMap
    fun progression =>
      (affineUnaryTripleProgressionRows progression).map
        transitionDispatchMuxCoordinateSeed

private theorem dispatchMux_progressionFrameStream_eq_seedEncoding
    (progression : AffineUnaryTripleProgression) :
    affineUnaryTripleProgressionFrameStream progression =
      encodeAffineUnaryTripleSeedFamily
        ((affineUnaryTripleProgressionRows progression).map
          transitionDispatchMuxCoordinateSeed) := by
  unfold affineUnaryTripleProgressionFrameStream
  generalize affineUnaryTripleProgressionRows progression = rows
  induction rows with
  | nil => rfl
  | cons row rest ih =>
      rcases row with ⟨first, second, third⟩
      simp only [List.flatMap_cons, List.map_cons,
        encodeAffineUnaryTripleSeedFamily]
      rw [ih]
      rfl

private theorem dispatchMux_progressionFamilyFrameStream_append
    (left right : List AffineUnaryTripleProgression) :
    affineUnaryTripleProgressionFamilyFrameStream (left ++ right) =
      affineUnaryTripleProgressionFamilyFrameStream left ++
        affineUnaryTripleProgressionFamilyFrameStream right := by
  induction left with
  | nil => rfl
  | cons progression rest ih =>
      simp [affineUnaryTripleProgressionFamilyFrameStream, ih,
        List.append_assoc]

private theorem dispatchMux_affineSeedFamily_append
    (left right : List AffineUnaryTripleSeed) :
    encodeAffineUnaryTripleSeedFamily (left ++ right) =
      encodeAffineUnaryTripleSeedFamily left ++
        encodeAffineUnaryTripleSeedFamily right := by
  induction left with
  | nil => rfl
  | cons seed rest ih =>
      simp [encodeAffineUnaryTripleSeedFamily, ih, List.append_assoc]

/-- Executing one row's mux progressions yields exactly its coordinate-seed
encoding. -/
theorem transitionDispatchMuxProgressionFrameStream_eq_coordinateSeeds
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    affineUnaryTripleProgressionFamilyFrameStream
        (transitionDispatchMuxAffineProgressions tm seed) =
      encodeAffineUnaryTripleSeedFamily
        (transitionDispatchMuxCoordinateSeeds tm seed) := by
  unfold transitionDispatchMuxCoordinateSeeds
  induction transitionDispatchMuxAffineProgressions tm seed with
  | nil => rfl
  | cons progression rest ih =>
      simp only [affineUnaryTripleProgressionFamilyFrameStream,
        List.flatMap_cons]
      rw [dispatchMux_progressionFrameStream_eq_seedEncoding, ih]
      exact (dispatchMux_affineSeedFamily_append _ _).symm

/-- The generated coordinate triples are exactly the fresh-coordinate fields
of the already verified semantic mux layout. -/
theorem transitionDispatchMuxCoordinateRows_eq_layouts
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (hwork : 0 < workHeight tm seed.height) :
    (transitionDispatchMuxAffineProgressions tm seed).flatMap
        affineUnaryTripleProgressionRows =
      (transitionDispatchMuxFreshLayoutsFromSeed tm seed).flatMap
        TransitionDispatchMuxFreshLayout.coordinates := by
  rw [transitionDispatchMuxAffineProgressions_eq_runtimes tm seed hwork]
  have hlayouts := transitionDispatchMuxRuntimes_layouts_eq tm seed
  have hcoordinates := congrArg
    (List.flatMap TransitionDispatchMuxFreshLayout.coordinates) hlayouts
  simpa [TransitionDispatchMuxRuntime.layout, List.flatMap_map] using
    hcoordinates

/-- Coordinate seeds read directly from the semantic seed-only mux layouts. -/
def transitionDispatchMuxLayoutCoordinateSeeds
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    List AffineUnaryTripleSeed :=
  (transitionDispatchMuxFreshLayoutsFromSeed tm seed).flatMap fun layout =>
    layout.coordinates.map transitionDispatchMuxCoordinateSeed

/-- Generated coordinate seeds are byte-for-byte the semantic layout
coordinates whenever the statement-cost affine forms are valid. -/
theorem transitionDispatchMuxCoordinateSeeds_eq_layout
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (hwork : 0 < workHeight tm seed.height) :
    transitionDispatchMuxCoordinateSeeds tm seed =
      transitionDispatchMuxLayoutCoordinateSeeds tm seed := by
  have hrows := transitionDispatchMuxCoordinateRows_eq_layouts tm seed hwork
  have hmapped := congrArg
    (List.map transitionDispatchMuxCoordinateSeed) hrows
  simpa [transitionDispatchMuxCoordinateSeeds,
    transitionDispatchMuxLayoutCoordinateSeeds, List.map_flatMap] using
    hmapped

/-- Forward fresh-coordinate stream for every verifier transition row. -/
noncomputable def verifierTransitionDispatchMuxCoordinateFrameStream
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List UnaryFrameSym :=
  affineUnaryTripleProgressionFamilyFrameStream
    ((verifierTransitionRowSeeds W input).flatMap
      (transitionDispatchMuxAffineProgressions W.machine.tm))

/-- The executed source is exactly the row-major generic seed encoding. -/
theorem verifierTransitionDispatchMuxCoordinateFrameStream_eq
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierTransitionDispatchMuxCoordinateFrameStream W input =
      encodeAffineUnaryTripleSeedFamily
        ((verifierTransitionRowSeeds W input).flatMap
          (transitionDispatchMuxCoordinateSeeds W.machine.tm)) := by
  unfold verifierTransitionDispatchMuxCoordinateFrameStream
  generalize verifierTransitionRowSeeds W input = seeds
  induction seeds with
  | nil => rfl
  | cons seed rest ih =>
      simp only [List.flatMap_cons]
      rw [dispatchMux_progressionFamilyFrameStream_append,
        transitionDispatchMuxProgressionFrameStream_eq_coordinateSeeds, ih,
        dispatchMux_affineSeedFamily_append]

/-- For verifier-produced rows, the concrete output stream is literally the
semantic fresh-coordinate layout encoding. -/
theorem verifierTransitionDispatchMuxCoordinateFrameStream_eq_layouts
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierTransitionDispatchMuxCoordinateFrameStream W input =
      encodeAffineUnaryTripleSeedFamily
        ((verifierTransitionRowSeeds W input).flatMap
          (transitionDispatchMuxLayoutCoordinateSeeds W.machine.tm)) := by
  rw [verifierTransitionDispatchMuxCoordinateFrameStream_eq]
  congr 1
  apply List.flatMap_congr
  intro seed hseed
  apply transitionDispatchMuxCoordinateSeeds_eq_layout
  have hheight := verifierTransitionRowSeeds_height_eq W input seed hseed
  rw [hheight]
  unfold workHeight
  exact Nat.add_pos_left (verifierHeight_eval_pos W input.length) _

/-- One fixed polynomial-time TM2 generates every dispatch-mux fresh
coordinate directly from the raw verifier input. -/
noncomputable def
    verifierTransitionDispatchMuxCoordinateFrameStream_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierTransitionDispatchMuxCoordinateFrameStream W) := by
  let descriptors :=
    verifierTransitionDispatchMuxDescriptorFrames_computableInPolyTime W
  let structured : _root_.Turing.TM2ComputableInPolyTime id
      encodeAffineUnaryTripleProgressionFamily
      (fun input =>
        (verifierTransitionRowSeeds W input).flatMap
          (transitionDispatchMuxAffineProgressions W.machine.tm)) :=
    { tm := descriptors.tm
      inputAlphabet := descriptors.inputAlphabet
      outputAlphabet := descriptors.outputAlphabet
      time := descriptors.time
      outputsFun := fun input => by
        have run := descriptors.outputsFun input
        simpa only [id_eq,
          verifierTransitionDispatchMuxDescriptorFrames_eq W input]
          using run }
  let composed :=
    _root_.Turing.TM2Comp.TM2ComputableInPolyTime.comp_scratch structured
      affineUnaryTripleProgressionFamilyFrameStream_computableInPolyTime
  let result := Classical.choice composed
  exact
    { tm := result.tm
      inputAlphabet := result.inputAlphabet
      outputAlphabet := result.outputAlphabet
      time := result.time
      outputsFun := fun input => by
        have run := result.outputsFun input
        simpa only [Function.comp_apply, id_eq,
          verifierTransitionDispatchMuxCoordinateFrameStream] using run }

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