Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_501380fdff864b7cb3d62d0b

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

/-!
# Fixed-delimiter affine transition sources

The basic transition affine-map source emits every numeric operand with an
ordinary unary separator.  Statement-controller payloads instead use fixed
mixtures of `tick`, `separator`, and `frameEnd`.  This module composes the
affine source with the verified cyclic delimiter transducer and proves that
one complete delimiter table is consumed for every transition row.

Literal control bytes can be represented by a zero affine operand followed
by that byte.  Consequently this compiler is the common source layer for the
fixed-layout statement phases without placing any runtime dimension in finite
control.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

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

/-- Evaluate a fixed affine form table on one transition seed and serialize
the resulting row with the verifier-fixed delimiter table. -/
def transitionAffineDelimitedMapRow
    (forms : List AffineUnaryTripleForm)
    (delimiters : List UnaryFrameSym) (seed : TransitionRowSeed) :
    List UnaryFrameSym :=
  encodeUnaryFrameWithFixedDelimiters
    (affineUnaryTripleMap forms (transitionTailAffineSeed seed)) delimiters

/-- Concrete raw-input target for a fixed delimiter-bearing affine row at
every adjacent tableau-row pair. -/
noncomputable def verifierTransitionAffineDelimitedMapFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (forms : List AffineUnaryTripleForm)
    (delimiters : List UnaryFrameSym)
    (hnonempty : 0 < delimiters.length)
    (input : List Γ) : List UnaryFrameSym :=
  rewriteUnaryFrameDelimiters delimiters hnonempty
    (verifierTransitionAffineMapFrames W forms input)

/-- The physical delimiter transducer resets after each fixed-width affine
row, so its output is literally the row-major fixed-delimiter target. -/
theorem verifierTransitionAffineDelimitedMapFrames_eq_rows
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (forms : List AffineUnaryTripleForm)
    (delimiters : List UnaryFrameSym)
    (hnonempty : 0 < delimiters.length)
    (haligned : forms.length = delimiters.length)
    (input : List Γ) :
    verifierTransitionAffineDelimitedMapFrames W forms delimiters hnonempty
        input =
      (verifierTransitionRowSeeds W input).flatMap
        (transitionAffineDelimitedMapRow forms delimiters) := by
  unfold verifierTransitionAffineDelimitedMapFrames
    verifierTransitionAffineMapFrames verifierTransitionTailAffineSeeds
  rw [rewriteUnaryFrameDelimiters_encodeUnaryFrame]
  let rows :=
    ((verifierTransitionRowSeeds W input).map transitionTailAffineSeed).map
      (affineUnaryTripleMap forms)
  have hrowsLength : ∀ row ∈ rows, row.length = delimiters.length := by
    intro row hrow
    simp only [rows, List.mem_map] at hrow
    rcases hrow with ⟨seed, _, rfl⟩
    simpa [affineUnaryTripleMap] using haligned
  rw [show affineUnaryTripleMapFamily forms
          ((verifierTransitionRowSeeds W input).map transitionTailAffineSeed) =
        rows.flatten by
      unfold affineUnaryTripleMapFamily rows
      exact flatMap_eq_map_flatten _ _]
  rw [encodeUnaryFrameWithDelimiterCycle_eq_fixedRows delimiters hnonempty
    rows hrowsLength]
  unfold rows
  rw [List.flatMap_map]
  rw [List.flatMap_map]
  rfl

/-- One fixed polynomial-time TM2 emits the complete delimiter-bearing
affine row family directly from the original verifier word. -/
noncomputable def
    verifierTransitionAffineDelimitedMapFrames_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (forms : List AffineUnaryTripleForm)
    (delimiters : List UnaryFrameSym)
    (hnonempty : 0 < delimiters.length) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierTransitionAffineDelimitedMapFrames W forms delimiters
        hnonempty) := by
  let source := verifierTransitionAffineMapFrames_computableInPolyTime W forms
  let delimited := unaryFrameDelimiterMap_computableInPolyTime delimiters
    hnonempty
  let composed :=
    _root_.Turing.TM2Comp.TM2ComputableInPolyTime.comp_scratch source
      delimited
  change _root_.Turing.TM2ComputableInPolyTime id id
    (fun input => rewriteUnaryFrameDelimiters delimiters hnonempty
      (verifierTransitionAffineMapFrames W forms input))
  simpa only [Function.comp_def] 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