Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_ac13eecbb48e82abd310aed6

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_f627e6e08a4b59ba4a2206e2
import Definitions.Def_PricingWithTips3DM_f34f433683fba432c5a857ff
import Definitions.Def_PricingWithTips3DM_af5818bae3aa12a58e6f911f
import Mathlib.Tactic
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Concrete three-way routing of transition-tail phases

Every phase coordinate is expanded to a tag and three fixed-width candidate
payloads.  The reusable router retains the narrowing prefix for tag zero, the
final-conjunction suffix for tag one, and the equality invocation for every
larger tag.  This module connects that finite controller to the raw verifier
input and proves the exact selected-field stream before identifying it with
the canonical transition script in the following module.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- One tag followed by the prefix, suffix, and equality candidate forms. -/
noncomputable def transitionTailPhaseTaggedForms
    (tm : _root_.Turing.FinTM2) : List AffineUnaryTripleForm :=
  transitionEqCoordinateTagForm ::
    (transitionTailPrefixPhaseForms tm ++
      transitionTailSuffixPhaseForms tm ++ transitionEqInvocationForms)

@[simp] theorem transitionTailPhaseTaggedForms_value
    (tm : _root_.Turing.FinTM2) (coordinate : AffineUnaryTripleSeed) :
    affineUnaryTripleMap (transitionTailPhaseTaggedForms tm) coordinate =
      coordinate.first ::
        (affineUnaryTripleMap (transitionTailPrefixPhaseForms tm) coordinate ++
          affineUnaryTripleMap (transitionTailSuffixPhaseForms tm) coordinate ++
            affineUnaryTripleMap transitionEqInvocationForms coordinate) := by
  simp [transitionTailPhaseTaggedForms, transitionEqCoordinateTagForm,
    affineUnaryTripleMap, affineUnaryTripleFormValue, List.map_append,
    List.append_assoc]

theorem transitionTailPrefixPhaseDelimiters_nonempty
    (tm : _root_.Turing.FinTM2) :
    0 < (transitionTailPrefixPhaseDelimiters tm).length := by
  simp [transitionTailPrefixPhaseDelimiters,
    transitionNarrowNotInvocationDelimiterTable]

theorem transitionTailSuffixPhaseDelimiters_nonempty
    (tm : _root_.Turing.FinTM2) :
    0 < (transitionTailSuffixPhaseDelimiters tm).length := by
  simp [transitionTailSuffixPhaseDelimiters]

/-- Typed router row denoted by one phase coordinate. -/
noncomputable def transitionTailPhaseTaggedRow
    (tm : _root_.Turing.FinTM2) (coordinate : AffineUnaryTripleSeed) :
    UnaryFrameThreeWayTaggedRow
      (transitionTailPrefixPhaseDelimiters tm).length
      (transitionTailSuffixPhaseDelimiters tm).length
      transitionEqInvocationDelimiterTable.length :=
  { tag := coordinate.first
    zeroValues :=
      affineUnaryTripleMap (transitionTailPrefixPhaseForms tm) coordinate
    oneValues :=
      affineUnaryTripleMap (transitionTailSuffixPhaseForms tm) coordinate
    manyValues := affineUnaryTripleMap transitionEqInvocationForms coordinate
    zero_length := by
      rw [show (affineUnaryTripleMap
            (transitionTailPrefixPhaseForms tm) coordinate).length =
          (transitionTailPrefixPhaseForms tm).length by
        simp [affineUnaryTripleMap]]
      exact transitionTailPrefixPhaseForms_delimiters_length tm
    one_length := by
      rw [show (affineUnaryTripleMap
            (transitionTailSuffixPhaseForms tm) coordinate).length =
          (transitionTailSuffixPhaseForms tm).length by
        simp [affineUnaryTripleMap]]
      exact transitionTailSuffixPhaseForms_delimiters_length tm
    many_length := by
      simp [affineUnaryTripleMap] }

/-- Router rows for the complete raw-input phase-coordinate family. -/
noncomputable def verifierTransitionTailPhaseTaggedRows
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List
      (UnaryFrameThreeWayTaggedRow
        (transitionTailPrefixPhaseDelimiters W.machine.tm).length
        (transitionTailSuffixPhaseDelimiters W.machine.tm).length
        transitionEqInvocationDelimiterTable.length) :=
  ((verifierTransitionRowSeeds W input).flatMap
    (transitionEqPhaseCoordinateSeeds W.machine.tm)).map
      (transitionTailPhaseTaggedRow W.machine.tm)

/-- Ordinary unary source bytes obtained by applying the complete candidate
form table to every phase coordinate. -/
noncomputable def verifierTransitionTailPhaseTaggedValueFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List UnaryFrameSym :=
  encodeUnaryFrame
    (affineUnaryTripleMapFamily
      (transitionTailPhaseTaggedForms W.machine.tm)
      ((verifierTransitionRowSeeds W input).flatMap
        (transitionEqPhaseCoordinateSeeds W.machine.tm)))

private theorem transitionTailPhaseTaggedValueEncoding
    (tm : _root_.Turing.FinTM2)
    (coordinates : List AffineUnaryTripleSeed) :
    encodeUnaryFrame
        (affineUnaryTripleMapFamily (transitionTailPhaseTaggedForms tm)
          coordinates) =
      encodeUnaryFrameThreeWayTaggedRowFamily
        (coordinates.map (transitionTailPhaseTaggedRow tm)) := by
  unfold affineUnaryTripleMapFamily
    encodeUnaryFrameThreeWayTaggedRowFamily
  rw [List.flatMap_map]
  unfold encodeUnaryFrame
  rw [List.flatMap_assoc]
  apply List.flatMap_congr
  intro coordinate _
  rw [transitionTailPhaseTaggedForms_value]
  rfl

/-- The affine-map source is literally the typed family encoding consumed by
the finite router. -/
theorem verifierTransitionTailPhaseTaggedValueFrames_eq_rows
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierTransitionTailPhaseTaggedValueFrames W input =
      encodeUnaryFrameThreeWayTaggedRowFamily
        (verifierTransitionTailPhaseTaggedRows W input) := by
  unfold verifierTransitionTailPhaseTaggedValueFrames
    verifierTransitionTailPhaseTaggedRows
  exact transitionTailPhaseTaggedValueEncoding W.machine.tm _

/-- One fixed polynomial-time TM2 emits the three candidate payloads for
every phase coordinate directly from the raw verifier word. -/
noncomputable def
    verifierTransitionTailPhaseTaggedValueFrames_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierTransitionTailPhaseTaggedValueFrames W) := by
  let coordinates :=
    verifierTransitionEqPhaseCoordinateFrameStream_computableInPolyTime W
  let structured : _root_.Turing.TM2ComputableInPolyTime id
      encodeAffineUnaryTripleSeedFamily
      (fun input =>
        (verifierTransitionRowSeeds W input).flatMap
          (transitionEqPhaseCoordinateSeeds W.machine.tm)) :=
    { tm := coordinates.tm
      inputAlphabet := coordinates.inputAlphabet
      outputAlphabet := coordinates.outputAlphabet
      time := coordinates.time
      outputsFun := fun input => by
        have run := coordinates.outputsFun input
        simpa only [id_eq,
          verifierTransitionEqPhaseCoordinateFrameStream_eq_seedEncoding
            W input] using run }
  let composed :=
    _root_.Turing.TM2Comp.TM2ComputableInPolyTime.comp_scratch structured
      (affineUnaryTripleMapFamily_computableInPolyTime
        (transitionTailPhaseTaggedForms W.machine.tm))
  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,
          verifierTransitionTailPhaseTaggedValueFrames] using run }

/-- Selected transition-tail fields after the concrete three-way router. -/
noncomputable def verifierTransitionTailPhaseRoutedInput
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List UnaryFrameSym :=
  rewriteUnaryFrameThreeWayTaggedRows
    (transitionTailPrefixPhaseDelimiters W.machine.tm)
    (transitionTailSuffixPhaseDelimiters W.machine.tm)
    transitionEqInvocationDelimiterTable
    (transitionTailPrefixPhaseDelimiters_nonempty W.machine.tm)
    (transitionTailSuffixPhaseDelimiters_nonempty W.machine.tm)
    transitionEqInvocationDelimiterTable_nonempty
    (verifierTransitionTailPhaseTaggedValueFrames W input)

/-- Exact typed semantics of the routed raw-input stream. -/
theorem verifierTransitionTailPhaseRoutedInput_eq_rows
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierTransitionTailPhaseRoutedInput W input =
      encodeUnaryFrameThreeWayTaggedRowOutputFamily
        (transitionTailPrefixPhaseDelimiters W.machine.tm)
        (transitionTailSuffixPhaseDelimiters W.machine.tm)
        transitionEqInvocationDelimiterTable
        (verifierTransitionTailPhaseTaggedRows W input) := by
  unfold verifierTransitionTailPhaseRoutedInput
  rw [verifierTransitionTailPhaseTaggedValueFrames_eq_rows]
  exact rewriteUnaryFrameThreeWayTaggedRows_family
    (transitionTailPrefixPhaseDelimiters W.machine.tm)
    (transitionTailSuffixPhaseDelimiters W.machine.tm)
    transitionEqInvocationDelimiterTable
    (transitionTailPrefixPhaseDelimiters_nonempty W.machine.tm)
    (transitionTailSuffixPhaseDelimiters_nonempty W.machine.tm)
    transitionEqInvocationDelimiterTable_nonempty _

/-- The complete selected phase stream is generated from the raw verifier
word by one fixed polynomial-time TM2. -/
noncomputable def
    verifierTransitionTailPhaseRoutedInput_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierTransitionTailPhaseRoutedInput W) := by
  let values :=
    verifierTransitionTailPhaseTaggedValueFrames_computableInPolyTime W
  let router := rewriteUnaryFrameThreeWayTaggedRows_computableInPolyTime
    (transitionTailPrefixPhaseDelimiters W.machine.tm)
    (transitionTailSuffixPhaseDelimiters W.machine.tm)
    transitionEqInvocationDelimiterTable
    (transitionTailPrefixPhaseDelimiters_nonempty W.machine.tm)
    (transitionTailSuffixPhaseDelimiters_nonempty W.machine.tm)
    transitionEqInvocationDelimiterTable_nonempty
  let composed :=
    _root_.Turing.TM2Comp.TM2ComputableInPolyTime.comp_scratch values router
  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_def,
          verifierTransitionTailPhaseRoutedInput] 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