Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_685547d5765fb4f5044243bf

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_55f98b1908fc52bb7cc02e72
import Definitions.Def_PricingWithTips3DM_729e94a489c14c165bcd23fa
import Definitions.Def_PricingWithTips3DM_8b95db31d7d948ed3e109173
import Definitions.Def_PricingWithTips3DM_bbaac3743d036b03526ad1a7
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Concrete exact-polynomial source for the symbolic initial boundary

The initial tableau row is emitted in four structural pieces: fixed control
bits, the symbolic input stack (which is compared with itself), empty height
bits for every other stack, and repeated blank cell blocks.  Every runtime
coordinate is an exact polynomial of the raw input length; only finite
machine data remains in finite control.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- Fixed number of non-stack coordinates in one configuration row. -/
def initialControlWidth (tm : _root_.Turing.FinTM2) : Nat :=
  1 + (labelCount tm + 1) + stateCount tm

/-- Exact affine width polynomial of one fixed machine stack. -/
def verifierInitialStackWidthPolynomial
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (k : W.machine.tm.K) : Polynomial Nat :=
  1 + Polynomial.C ((reachableAlphabet W.machine.tm k).card + 2) *
    verifierHeight W

@[simp] theorem verifierInitialStackWidthPolynomial_eval
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (k : W.machine.tm.K) (n : Nat) :
    (verifierInitialStackWidthPolynomial W k).eval n =
      cfgStackBitWidth W.machine.tm ((verifierHeight W).eval n) k := by
  simp [verifierInitialStackWidthPolynomial, cfgStackBitWidth,
    Polynomial.eval_add, Polynomial.eval_mul]
  ring

/-- First in-row coordinate of one fixed stack. -/
noncomputable def verifierInitialStackOffsetPolynomial
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (k : W.machine.tm.K) : Polynomial Nat :=
  Polynomial.C
      (initialControlWidth W.machine.tm + arithmeticStackOrdinal W.machine.tm k) +
    Polynomial.C (cfgStackBitOffsetHeightCoeff W.machine.tm k) *
      verifierHeight W

@[simp] theorem verifierInitialStackOffsetPolynomial_eval
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (k : W.machine.tm.K) (n : Nat) :
    (verifierInitialStackOffsetPolynomial W k).eval n =
      initialControlWidth W.machine.tm +
        cfgStackBitOffset W.machine.tm ((verifierHeight W).eval n) k := by
  rw [cfgStackBitOffset_eq_affine]
  simp [verifierInitialStackOffsetPolynomial,
    Polynomial.eval_add, Polynomial.eval_mul]
  ring

/-- Equality carry immediately before one in-row coordinate. -/
def verifierInitialPreviousPolynomial
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (coordinate : Polynomial Nat) : Polynomial Nat :=
  verifierTransitionEndPolynomial W + Polynomial.C 6 * coordinate

/-- False-pool wire; the true-pool wire is its successor. -/
def verifierInitialFalseWirePolynomial
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) : Polynomial Nat :=
  verifierTableauInputPolynomial W

/-- Select the false or true pool wire from the auxiliary seed coordinate. -/
def initialPoolTargetForm : Bool → AffineUnaryTripleForm
  | false => { constant := 0, first := 0, second := 0, third := 1 }
  | true => { constant := 1, first := 0, second := 0, third := 1 }

/-- Canonical non-stack bits of an initial machine configuration. -/
noncomputable def initialControlBits
    (tm : _root_.Turing.FinTM2) : List Bool :=
  [false] ++
    List.ofFn (encodeOneHot (encodeLabel tm (some tm.main))) ++
    List.ofFn (encodeOneHot (stateEquivFin tm tm.initialState))

/-- Fixed affine right-target table for the non-stack prefix. -/
noncomputable def initialControlTargetForms
    (tm : _root_.Turing.FinTM2) : List AffineUnaryTripleForm :=
  (initialControlBits tm).map initialPoolTargetForm

/-- Fixed blank one-hot target table of a physical cell. -/
noncomputable def initialBlankCellTargetForms
    (tm : _root_.Turing.FinTM2) (k : tm.K) :
    List AffineUnaryTripleForm :=
  List.ofFn fun symbol : Fin ((reachableAlphabet tm k).card + 1) =>
    initialPoolTargetForm (decide (symbol.val = (reachableAlphabet tm k).card))

/-- Exact encoded equality frames for the fixed control prefix. -/
def verifierInitialControlInput
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List UnaryFrameSym :=
  exactPolynomialAffineEqFinRowInput
    (initialControlTargetForms W.machine.tm)
    (verifierTransitionEndPolynomial W) 0
    (verifierInitialFalseWirePolynomial W)
    0 0 0 1 input

/-- Exact encoded equality frames for the symbolic input stack.  Its target
is the same first-row stack, so left and right progress together. -/
def verifierInitialInputStackInput
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List UnaryFrameSym :=
  let coordinate := verifierInitialStackOffsetPolynomial W W.machine.tm.k₀
  exactPolynomialAffineEqFinInput
    (verifierInitialPreviousPolynomial W coordinate)
    coordinate coordinate
    6 1 1
    (verifierInitialStackWidthPolynomial W W.machine.tm.k₀) input

/-- Equality input for the selected-zero height coordinate of an empty stack. -/
def verifierInitialEmptyStackHeightZeroInput
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (k : W.machine.tm.K) (input : List Γ) : List UnaryFrameSym :=
  let coordinate := verifierInitialStackOffsetPolynomial W k
  exactPolynomialAffineEqFinInput
    (verifierInitialPreviousPolynomial W coordinate)
    coordinate (verifierInitialFalseWirePolynomial W + 1)
    0 0 0 1 input

/-- Equality input for all unselected positive height coordinates of an empty
stack. -/
def verifierInitialEmptyStackHeightTailInput
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (k : W.machine.tm.K) (input : List Γ) : List UnaryFrameSym :=
  let coordinate := verifierInitialStackOffsetPolynomial W k + 1
  exactPolynomialAffineEqFinInput
    (verifierInitialPreviousPolynomial W coordinate)
    coordinate (verifierInitialFalseWirePolynomial W)
    6 1 0 (verifierHeight W) input

/-- Equality input for all physical cells of an empty stack.  Each runtime
cell expands to the fixed false/.../false/blank-true symbol row. -/
def verifierInitialEmptyStackCellsInput
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (k : W.machine.tm.K) (input : List Γ) : List UnaryFrameSym :=
  let width := (reachableAlphabet W.machine.tm k).card + 1
  let coordinate := verifierInitialStackOffsetPolynomial W k +
    verifierHeight W + 1
  exactPolynomialAffineEqFinRowInput
    (initialBlankCellTargetForms W.machine.tm k)
    (verifierInitialPreviousPolynomial W coordinate)
    coordinate (verifierInitialFalseWirePolynomial W)
    (Polynomial.C (6 * width)) (Polynomial.C width) 0
    (verifierHeight W) input

/-- Complete equality input for one fixed stack. -/
def verifierInitialStackInput
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (k : W.machine.tm.K) (input : List Γ) : List UnaryFrameSym :=
  if _hk : k = W.machine.tm.k₀ then
    verifierInitialInputStackInput W input
  else
    verifierInitialEmptyStackHeightZeroInput W k input ++
      verifierInitialEmptyStackHeightTailInput W k input ++
      verifierInitialEmptyStackCellsInput W k input

/-- Stack blocks in the canonical fixed-machine enumeration. -/
def verifierInitialStackFamilyInput
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List UnaryFrameSym :=
  (arithmeticRuntimeStackSourceIndices W.machine.tm).flatMap fun index =>
    verifierInitialStackInput W
      ((arithmeticStackEquiv W.machine.tm).symm index) input

/-- Complete exact-polynomial input for the established initial-boundary
equality controller. -/
def verifierInitialBoundaryInputTarget
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List UnaryFrameSym :=
  verifierInitialControlInput W input ++
    verifierInitialStackFamilyInput W input

/-- The fixed control-prefix equality input is polynomial-time computable. -/
noncomputable def verifierInitialControlInput_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierInitialControlInput W) := by
  letI : Fintype Γ := W.alphabetFintype
  exact exactPolynomialAffineEqFinRowInput_computableInPolyTime
    (initialControlTargetForms W.machine.tm)
    (verifierTransitionEndPolynomial W) 0
    (verifierInitialFalseWirePolynomial W)
    0 0 0 1

/-- The symbolic input-stack equality input is polynomial-time computable. -/
noncomputable def verifierInitialInputStackInput_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierInitialInputStackInput W) := by
  letI : Fintype Γ := W.alphabetFintype
  exact exactPolynomialAffineEqFinInput_computableInPolyTime
    (verifierInitialPreviousPolynomial W
      (verifierInitialStackOffsetPolynomial W W.machine.tm.k₀))
    (verifierInitialStackOffsetPolynomial W W.machine.tm.k₀)
    (verifierInitialStackOffsetPolynomial W W.machine.tm.k₀)
    6 1 1 (verifierInitialStackWidthPolynomial W W.machine.tm.k₀)

/-- The complete empty-stack equality input is polynomial-time computable. -/
noncomputable def verifierInitialEmptyStackInput_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (k : W.machine.tm.K) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (fun input : List Γ =>
        verifierInitialEmptyStackHeightZeroInput W k input ++
          verifierInitialEmptyStackHeightTailInput W k input ++
          verifierInitialEmptyStackCellsInput W k input) := by
  letI : Fintype Γ := W.alphabetFintype
  let coordinate := verifierInitialStackOffsetPolynomial W k
  let zeroSource := exactPolynomialAffineEqFinInput_computableInPolyTime
    (Γ := Γ)
    (verifierInitialPreviousPolynomial W coordinate)
    coordinate (verifierInitialFalseWirePolynomial W + 1)
    0 0 0 1
  let tailCoordinate := coordinate + 1
  let tailSource := exactPolynomialAffineEqFinInput_computableInPolyTime
    (Γ := Γ)
    (verifierInitialPreviousPolynomial W tailCoordinate)
    tailCoordinate (verifierInitialFalseWirePolynomial W)
    6 1 0 (verifierHeight W)
  let width := (reachableAlphabet W.machine.tm k).card + 1
  let cellCoordinate := coordinate + verifierHeight W + 1
  let cellSource := exactPolynomialAffineEqFinRowInput_computableInPolyTime
    (Γ := Γ) (initialBlankCellTargetForms W.machine.tm k)
    (verifierInitialPreviousPolynomial W cellCoordinate)
    cellCoordinate (verifierInitialFalseWirePolynomial W)
    (Polynomial.C (6 * width)) (Polynomial.C width) 0
    (verifierHeight W)
  let first := unaryFrameSameInputConcat_computableInPolyTime
    zeroSource tailSource
  let result := unaryFrameSameInputConcat_computableInPolyTime first cellSource
  simpa [coordinate, tailCoordinate, cellCoordinate,
    verifierInitialEmptyStackHeightZeroInput,
    verifierInitialEmptyStackHeightTailInput,
    verifierInitialEmptyStackCellsInput, width, List.append_assoc] using result

/-- One fixed stack block has a concrete polynomial-time source. -/
noncomputable def verifierInitialStackInput_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (k : W.machine.tm.K) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierInitialStackInput W k) := by
  letI : Fintype Γ := W.alphabetFintype
  by_cases hk : k = W.machine.tm.k₀
  · let source := verifierInitialInputStackInput_computableInPolyTime W
    exact
      { tm := source.tm
        inputAlphabet := source.inputAlphabet
        outputAlphabet := source.outputAlphabet
        time := source.time
        outputsFun := fun input => by
          have run := source.outputsFun input
          simpa [verifierInitialStackInput, hk] using run }
  · let source := verifierInitialEmptyStackInput_computableInPolyTime W k
    exact
      { tm := source.tm
        inputAlphabet := source.inputAlphabet
        outputAlphabet := source.outputAlphabet
        time := source.time
        outputsFun := fun input => by
          have run := source.outputsFun input
          simpa [verifierInitialStackInput, hk, List.append_assoc] using run }

/-- The fixed finite family of all stack blocks is polynomial-time
computable. -/
noncomputable def verifierInitialStackFamilyInput_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierInitialStackFamilyInput W) := by
  letI : Fintype Γ := W.alphabetFintype
  let indices := arithmeticRuntimeStackSourceIndices W.machine.tm
  change _root_.Turing.TM2ComputableInPolyTime id id
    (fun input : List Γ => indices.flatMap fun index =>
      verifierInitialStackInput W
        ((arithmeticStackEquiv W.machine.tm).symm index) input)
  induction indices with
  | nil =>
      let empty := exactPolynomialAffineEqFinInput_computableInPolyTime
        (Γ := Γ) 0 0 0 0 0 0 0
      exact
        { tm := empty.tm
          inputAlphabet := empty.inputAlphabet
          outputAlphabet := empty.outputAlphabet
          time := empty.time
          outputsFun := fun input => by
            have run := empty.outputsFun input
            simpa [exactPolynomialAffineEqFinInput,
              exactPolynomialAffineEqFinFrames, eqFinProgressionFrames,
              eqFinProgressionSeeds,
              exactPolynomialAffineUnaryTripleProgression,
              affineUnaryTripleProgressionRows,
              affineUnaryTripleProgressionRowsFrom,
              encodeAffineEqFinFrames] using run }
  | cons index rest ih =>
      let head := verifierInitialStackInput_computableInPolyTime W
        ((arithmeticStackEquiv W.machine.tm).symm index)
      let combined := unaryFrameSameInputConcat_computableInPolyTime head ih
      simpa only [List.flatMap_cons] using combined

/-- A single fixed polynomial-time TM2 compiles every canonical equality
frame of the symbolic initial boundary from the raw verifier word. -/
noncomputable def verifierInitialBoundaryInputTarget_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierInitialBoundaryInputTarget W) := by
  letI : Fintype Γ := W.alphabetFintype
  exact unaryFrameSameInputConcat_computableInPolyTime
    (verifierInitialControlInput_computableInPolyTime W)
    (verifierInitialStackFamilyInput_computableInPolyTime W)

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