Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_f34f433683fba432c5a857ff

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_0d878c712ea6e5d2ff7ff4fc
import Definitions.Def_PricingWithTips3DM_8a431b2515253bbdce9fce33
import Definitions.Def_PricingWithTips3DM_84be08924fd1ac1c9e9f18bd
import Mathlib.Tactic
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Tagged transition equality rows

The marked coordinate source ends every tableau row with the fixed coordinate
`(0, 0, 0)`.  This module prefixes every equality payload by its first
coordinate.  Real equality coordinates have a positive first coordinate,
whereas the sentinel has tag zero.  A reusable finite-state pass can therefore
drop real tags and turn precisely the sentinels into outer `frameEnd`s.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- The first coordinate, used as a zero-versus-positive row tag. -/
def transitionEqCoordinateTagForm : AffineUnaryTripleForm :=
  { constant := 0, first := 1, second := 0, third := 0 }

/-- One tag followed by the nine ordinary equality invocation operands. -/
def transitionEqTaggedInvocationForms : List AffineUnaryTripleForm :=
  transitionEqCoordinateTagForm :: transitionEqInvocationForms

@[simp] theorem transitionEqTaggedInvocationForms_value
    (seed : AffineUnaryTripleSeed) :
    affineUnaryTripleMap transitionEqTaggedInvocationForms seed =
      seed.first ::
        affineUnaryTripleMap transitionEqInvocationForms seed := by
  simp [transitionEqTaggedInvocationForms,
    transitionEqCoordinateTagForm, affineUnaryTripleMap,
    affineUnaryTripleFormValue]

@[simp] theorem transitionEqInvocationForms_length :
    transitionEqInvocationForms.length = 9 := rfl

private theorem encodeUnaryFrame_flatMap {alpha : Type}
    (items : List alpha) (values : alpha → List Nat) :
    encodeUnaryFrame (items.flatMap values) =
      items.flatMap fun item => encodeUnaryFrame (values item) := by
  unfold encodeUnaryFrame
  rw [List.flatMap_assoc]

private theorem transitionEqTaggedValueEncoding
    (coordinates : List AffineUnaryTripleSeed) :
    encodeUnaryFrame
        (affineUnaryTripleMapFamily transitionEqTaggedInvocationForms
          coordinates) =
      (coordinates.map fun coordinate =>
        (coordinate.first,
          affineUnaryTripleMap transitionEqInvocationForms coordinate)).flatMap
        fun row => encodeUnaryFrame (row.1 :: row.2) := by
  unfold affineUnaryTripleMapFamily
  rw [encodeUnaryFrame_flatMap]
  simp only [List.flatMap_map]
  apply List.flatMap_congr
  intro coordinate _
  rw [transitionEqTaggedInvocationForms_value]

/-- Every semantic equality coordinate is distinguishable from the zero
sentinel by its first component. -/
theorem transitionEqCoordinateSeed_first_pos
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (coordinate : AffineUnaryTripleSeed)
    (hcoordinate : coordinate ∈ transitionEqCoordinateSeeds tm seed)
    (hwork : 0 < workHeight tm seed.height) :
    0 < coordinate.first := by
  rw [transitionEqCoordinateSeeds_eq_slots tm seed hwork] at hcoordinate
  simp only [List.mem_map] at hcoordinate
  rcases hcoordinate with ⟨slot, _, rfl⟩
  simp only [transitionEqSlotSeed, transitionEqStart,
    transitionNarrowStart]
  omega

/-- Raw tagged values obtained by applying one fixed affine form table to all
row-marked coordinate seeds. -/
noncomputable def verifierTransitionEqRowTaggedValueFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List UnaryFrameSym :=
  encodeUnaryFrame
    (affineUnaryTripleMapFamily transitionEqTaggedInvocationForms
      ((verifierTransitionRowSeeds W input).flatMap
        (transitionEqRowMarkedCoordinateSeeds W.machine.tm)))

/-- Typed tagged-row family consumed by the generic zero-tag demultiplexer. -/
noncomputable def verifierTransitionEqTaggedRowFamily
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : UnaryFrameZeroTagRowFamily 9 :=
  { rows := (verifierTransitionRowSeeds W input).flatMap fun seed =>
      (transitionEqRowMarkedCoordinateSeeds W.machine.tm seed).map fun
        coordinate =>
          (coordinate.first,
            affineUnaryTripleMap transitionEqInvocationForms coordinate)
    payload_lengths := by
      intro row hrow
      simp only [List.mem_flatMap, List.mem_map] at hrow
      rcases hrow with ⟨seed, _, coordinate, _, rfl⟩
      simp [affineUnaryTripleMap] }

/-- The affine-map output is literally the typed family encoding expected by
the demultiplexer. -/
theorem verifierTransitionEqRowTaggedValueFrames_eq_family
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierTransitionEqRowTaggedValueFrames W input =
      encodeUnaryFrameZeroTagRowFamily
        (verifierTransitionEqTaggedRowFamily W input) := by
  unfold verifierTransitionEqRowTaggedValueFrames
    verifierTransitionEqTaggedRowFamily
    encodeUnaryFrameZeroTagRowFamily
  rw [transitionEqTaggedValueEncoding, List.map_flatMap]

/-- One fixed polynomial-time TM2 emits all tagged rows directly from the raw
verifier input. -/
noncomputable def
    verifierTransitionEqRowTaggedValueFrames_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierTransitionEqRowTaggedValueFrames W) := by
  let coordinates :=
    verifierTransitionEqRowMarkedCoordinateFrameStream_computableInPolyTime W
  let structured : _root_.Turing.TM2ComputableInPolyTime id
      encodeAffineUnaryTripleSeedFamily
      (fun input =>
        (verifierTransitionRowSeeds W input).flatMap
          (transitionEqRowMarkedCoordinateSeeds 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,
          verifierTransitionEqRowMarkedCoordinateFrameStream_eq_seedEncoding
            W input] using run }
  let composed :=
    _root_.Turing.TM2Comp.TM2ComputableInPolyTime.comp_scratch structured
      (affineUnaryTripleMapFamily_computableInPolyTime
        transitionEqTaggedInvocationForms)
  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,
          verifierTransitionEqRowTaggedValueFrames] using run }

/-- Drop positive coordinate tags and materialize zero sentinels as outer row
boundaries. -/
noncomputable def verifierTransitionEqRowMarkedValueFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List UnaryFrameSym :=
  rewriteUnaryFrameZeroTagRows 9
    (verifierTransitionEqRowTaggedValueFrames W input)

private theorem transitionEqRealTaggedRows_output
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (hwork : 0 < workHeight tm seed.height) :
    ((transitionEqCoordinateSeeds tm seed).map fun coordinate =>
        (coordinate.first,
          affineUnaryTripleMap transitionEqInvocationForms coordinate)).flatMap
        (fun row =>
          if row.1 = 0 then [.frameEnd]
          else encodeUnaryFrame row.2) =
      encodeUnaryFrame
        (affineUnaryTripleMapFamily transitionEqInvocationForms
          (transitionEqCoordinateSeeds tm seed)) := by
  unfold affineUnaryTripleMapFamily
  rw [encodeUnaryFrame_flatMap]
  rw [List.flatMap_map]
  apply List.flatMap_congr
  intro coordinate hcoordinate
  have hpositive := transitionEqCoordinateSeed_first_pos tm seed coordinate
    hcoordinate hwork
  simp [hpositive.ne']

private theorem transitionEqMarkedTaggedRows_output
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (hwork : 0 < workHeight tm seed.height) :
    ((transitionEqRowMarkedCoordinateSeeds tm seed).map fun coordinate =>
        (coordinate.first,
          affineUnaryTripleMap transitionEqInvocationForms coordinate)).flatMap
        (fun row =>
          if row.1 = 0 then [.frameEnd]
          else encodeUnaryFrame row.2) =
      encodeUnaryFrame
          (affineUnaryTripleMapFamily transitionEqInvocationForms
            (transitionEqCoordinateSeeds tm seed)) ++
        [.frameEnd] := by
  unfold transitionEqRowMarkedCoordinateSeeds
  rw [List.map_append, List.flatMap_append,
    transitionEqRealTaggedRows_output tm seed hwork]
  simp [transitionEqSentinelCoordinateSeed]

/-- Exact row-major semantics after demultiplexing: nine ordinary operand
fields per equality frame and one explicit `frameEnd` after every tableau
row. -/
theorem verifierTransitionEqRowMarkedValueFrames_eq_rows
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierTransitionEqRowMarkedValueFrames W input =
      (verifierTransitionRowSeeds W input).flatMap fun seed =>
        encodeUnaryFrame
            (affineUnaryTripleMapFamily transitionEqInvocationForms
              (transitionEqCoordinateSeeds W.machine.tm seed)) ++
          [.frameEnd] := by
  unfold verifierTransitionEqRowMarkedValueFrames
  rw [verifierTransitionEqRowTaggedValueFrames_eq_family,
    rewriteUnaryFrameZeroTagRows_family
      (verifierTransitionEqTaggedRowFamily W input) (by omega)]
  unfold encodeUnaryFrameZeroTagRowOutput
    verifierTransitionEqTaggedRowFamily
  rw [List.flatMap_assoc]
  apply List.flatMap_congr
  intro seed hseed
  apply transitionEqMarkedTaggedRows_output
  rw [verifierTransitionRowSeeds_height_eq W input seed hseed]
  exact Nat.add_pos_left
    (verifierHeight_eval_pos W input.length)
    (maxPushesPerStep W.machine.tm)

/-- The row-marked ordinary equality values are generated by one fixed
polynomial-time TM2 from the raw verifier word. -/
noncomputable def
    verifierTransitionEqRowMarkedValueFrames_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierTransitionEqRowMarkedValueFrames W) := by
  let tagged :=
    verifierTransitionEqRowTaggedValueFrames_computableInPolyTime W
  let demux := rewriteUnaryFrameZeroTagRows_computableInPolyTime 9
  let composed :=
    _root_.Turing.TM2Comp.TM2ComputableInPolyTime.comp_scratch tagged demux
  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,
          verifierTransitionEqRowMarkedValueFrames] 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