Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_d2ae7b422d26e98396abef2f

by qmaai2907271020 · Oct 23, 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_39b9c4b37fbdd91ca7a2f747
import Definitions.Def_PricingWithTips3DM_86ede598e04b85255b0e5f32
import Mathlib.Tactic
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Alignment of the concrete accepting source

The positive accepting source is organized by control, height, and cell
segments.  This module identifies its fixed Boolean target tables with the
canonical encoding of `haltList [true]`, before closing the complete frame
family against the semantic optional operand.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- Arithmetic Boolean-pool target of one accepting-row slot. -/
def verifierAcceptingSlotRightWire
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (hmember : verifierAcceptingSymbol W ∈
      reachableAlphabet W.machine.tm W.machine.tm.k₁)
    (input : List Γ)
    (slot : CfgSlot W.machine.tm ((verifierHeight W).eval input.length)) : Nat :=
  let tm := W.machine.tm
  let falseWire := (verifierInitialFalseWirePolynomial W).eval input.length
  let trueWire := falseWire + 1
  let outputCode := encodeAlphabetSymbol tm tm.k₁
    (verifierAcceptingSymbol W) hmember
  match slot with
  | .inl _ => trueWire
  | .inr (.inl label) =>
      if label = encodeLabel tm none then trueWire else falseWire
  | .inr (.inr (.inl state)) =>
      if state = stateEquivFin tm tm.initialState then trueWire else falseWire
  | .inr (.inr (.inr ⟨k, .inl height⟩)) =>
      if _ : k = tm.k₁ then
        if height.val = 1 then trueWire else falseWire
      else if height.val = 0 then trueWire else falseWire
  | .inr (.inr (.inr ⟨k, .inr (cell, symbol)⟩)) =>
      if _ : k = tm.k₁ then
        if cell.val = 0 then
          if symbol.val = outputCode.val then trueWire else falseWire
        else if symbol.val = (reachableAlphabet tm k).card then
          trueWire
        else falseWire
      else if symbol.val = (reachableAlphabet tm k).card then
        trueWire
      else falseWire

/-- The arithmetic target is the proof-carrying static halt target wire. -/
theorem verifierAcceptingSlotRightWire_eq_semantic
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (hmember : verifierAcceptingSymbol W ∈
      reachableAlphabet W.machine.tm W.machine.tm.k₁)
    (input : List Γ)
    (slot : CfgSlot W.machine.tm ((verifierHeight W).eval input.length)) :
    verifierAcceptingSlotRightWire W hmember input slot =
      verifierAcceptingTargetWires W input
        (verifierAcceptingOutputFitsOfSymbol W input hmember) slot := by
  rcases slot with (_ | label | state | ⟨k, height | cell⟩)
  · simp [verifierAcceptingSlotRightWire, CfgSlot.halted,
      verifierAcceptingTargetWires, staticBoundedCfgWires,
      staticCfgWires, encodeRawCfgBits, encodeCfg,
      _root_.Turing.haltList, labelHalted]
  · by_cases hlabel :
      label = encodeLabel W.machine.tm none
    <;> simp [verifierAcceptingSlotRightWire, CfgSlot.label,
      verifierAcceptingTargetWires, staticBoundedCfgWires,
      staticCfgWires, encodeRawCfgBits, encodeCfg,
      _root_.Turing.haltList, encodeOneHot, hlabel]
  · by_cases hstate :
      state = stateEquivFin W.machine.tm W.machine.tm.initialState
    <;> simp [verifierAcceptingSlotRightWire, CfgSlot.state,
      verifierAcceptingTargetWires, staticBoundedCfgWires,
      staticCfgWires, encodeRawCfgBits, encodeCfg,
      _root_.Turing.haltList, encodeOneHot, hstate]
  · by_cases hk : k = W.machine.tm.k₁
    · subst k
      by_cases hheight : height.val = 1
      <;> simp [verifierAcceptingSlotRightWire, CfgSlot.stackHeight,
        verifierAcceptingTargetWires, staticBoundedCfgWires,
        staticCfgWires, encodeRawCfgBits, encodeCfg,
        _root_.Turing.haltList, encodeBoundedStack, encodeOneHot,
        hheight, Fin.ext_iff]
    · by_cases hheight : height.val = 0
      · have hfin : height = 0 := Fin.ext hheight
        simp [verifierAcceptingSlotRightWire, CfgSlot.stackHeight,
          verifierAcceptingTargetWires, staticBoundedCfgWires,
          staticCfgWires, encodeRawCfgBits, encodeCfg,
          _root_.Turing.haltList, encodeBoundedStack, encodeOneHot,
          hk, hheight, hfin]
      · have hfin : height ≠ 0 := fun heq =>
          hheight (congrArg Fin.val heq)
        simp [verifierAcceptingSlotRightWire, CfgSlot.stackHeight,
          verifierAcceptingTargetWires, staticBoundedCfgWires,
          staticCfgWires, encodeRawCfgBits, encodeCfg,
          _root_.Turing.haltList, encodeBoundedStack, encodeOneHot,
          hk, hheight, hfin]
  · rcases cell with ⟨cell, symbol⟩
    by_cases hk : k = W.machine.tm.k₁
    · subst k
      by_cases hcell : cell.val = 0
      · by_cases hsymbol : symbol.val =
            (encodeAlphabetSymbol W.machine.tm W.machine.tm.k₁
              (verifierAcceptingSymbol W) hmember).val
        <;> simp [verifierAcceptingSlotRightWire, CfgSlot.stackCell,
          verifierAcceptingTargetWires, staticBoundedCfgWires,
          staticCfgWires, encodeRawCfgBits, encodeCfg,
          _root_.Turing.haltList, encodeBoundedStack, encodeOneHot,
          hcell, hsymbol, Fin.ext_iff]
      · by_cases hsymbol : symbol.val =
          (reachableAlphabet W.machine.tm W.machine.tm.k₁).card
        <;> simp [verifierAcceptingSlotRightWire, CfgSlot.stackCell,
          verifierAcceptingTargetWires, staticBoundedCfgWires,
          staticCfgWires, encodeRawCfgBits, encodeCfg,
          _root_.Turing.haltList, encodeBoundedStack, encodeOneHot,
          hcell, hsymbol, Fin.ext_iff]
    · by_cases hsymbol :
        symbol.val = (reachableAlphabet W.machine.tm k).card
      <;> simp [verifierAcceptingSlotRightWire, CfgSlot.stackCell,
        verifierAcceptingTargetWires, staticBoundedCfgWires,
        staticCfgWires, encodeRawCfgBits, encodeCfg,
        _root_.Turing.haltList, encodeBoundedStack, encodeOneHot,
        hk, hsymbol, Fin.ext_iff]

/-! ## Frames denoted by the concrete source -/

/-- Arithmetic accepting frame at one in-row coordinate. -/
def verifierAcceptingFrameAtCoordinate
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) (coordinate right : Nat) : AffineEqFinPairFrame :=
  let previous := verifierInputBoundaryEnd W input + 6 * coordinate
  { eqStart := previous + 1
    left := (verifierLastRowStartPolynomial W).eval input.length + coordinate
    right := right
    matched := previous + 5
    previous := previous }

/-- The explicit public-slot frame is the arithmetic coordinate frame with
the corresponding arithmetic Boolean-pool target. -/
theorem verifierAcceptingSlotFrame_eq_arithmetic
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (hmember : verifierAcceptingSymbol W ∈
      reachableAlphabet W.machine.tm W.machine.tm.k₁)
    (input : List Γ)
    (slot : CfgSlot W.machine.tm ((verifierHeight W).eval input.length)) :
    verifierAcceptingSlotFrame W hmember input slot =
      verifierAcceptingFrameAtCoordinate W input
        (cfgSlotEquivFin W.machine.tm
          ((verifierHeight W).eval input.length) slot).val
        (verifierAcceptingSlotRightWire W hmember input slot) := by
  unfold verifierAcceptingSlotFrame verifierAcceptingFrameAtCoordinate
  rw [verifierAcceptingSlotRightWire_eq_semantic]

/-- Frames denoted by an ordinary accepting progression segment. -/
def verifierAcceptingSegmentFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (coordinate right stepRight count : Polynomial Nat)
    (input : List Γ) : List AffineEqFinPairFrame :=
  dynamicFirstAffineEqFinFrames
    (verifierAcceptingPrevious W coordinate)
    (verifierLastRowStartPolynomial W + coordinate)
    right 6 1 stepRight count input

/-- Frames denoted by an accepting row-block segment. -/
def verifierAcceptingRowSegmentFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (forms : List AffineUnaryTripleForm)
    (coordinate aux stepPrevious stepLeft stepAux count : Polynomial Nat)
    (input : List Γ) : List AffineEqFinPairFrame :=
  dynamicFirstAffineEqFinRowFrames forms
    (verifierAcceptingPrevious W coordinate)
    (verifierLastRowStartPolynomial W + coordinate)
    aux stepPrevious stepLeft stepAux count input

def verifierAcceptingControlCompiledFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List AffineEqFinPairFrame :=
  verifierAcceptingRowSegmentFrames W
    (acceptingControlTargetForms W.machine.tm)
    0 (verifierInitialFalseWirePolynomial W) 0 0 0 1 input

def verifierAcceptingEmptyStackCompiledFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (k : W.machine.tm.K) (input : List Γ) : List AffineEqFinPairFrame :=
  let coordinate := verifierInitialStackOffsetPolynomial W k
  let cells := coordinate + verifierHeight W + 1
  verifierAcceptingSegmentFrames W coordinate
      (verifierInitialFalseWirePolynomial W + 1) 0 1 input ++
    verifierAcceptingSegmentFrames W (coordinate + 1)
      (verifierInitialFalseWirePolynomial W) 0 (verifierHeight W) input ++
    verifierAcceptingRowSegmentFrames W
      (initialBlankCellTargetForms W.machine.tm k)
      cells (verifierInitialFalseWirePolynomial W)
      (Polynomial.C
        (6 * ((reachableAlphabet W.machine.tm k).card + 1)))
      (Polynomial.C ((reachableAlphabet W.machine.tm k).card + 1))
      0 (verifierHeight W) input

def verifierAcceptingOutputStackCompiledFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (hmember : verifierAcceptingSymbol W ∈
      reachableAlphabet W.machine.tm W.machine.tm.k₁)
    (input : List Γ) : List AffineEqFinPairFrame :=
  let k := W.machine.tm.k₁
  let width := (reachableAlphabet W.machine.tm k).card + 1
  let coordinate := verifierInitialStackOffsetPolynomial W k
  let cells := coordinate + verifierHeight W + 1
  verifierAcceptingSegmentFrames W coordinate
      (verifierInitialFalseWirePolynomial W) 0 1 input ++
    verifierAcceptingSegmentFrames W (coordinate + 1)
      (verifierInitialFalseWirePolynomial W + 1) 0 1 input ++
    verifierAcceptingSegmentFrames W (coordinate + 2)
      (verifierInitialFalseWirePolynomial W) 0
      (verifierAcceptingHeightTailPolynomial W) input ++
    verifierAcceptingRowSegmentFrames W
      (acceptingOutputCellTargetForms W hmember)
      cells (verifierInitialFalseWirePolynomial W) 0 0 0 1 input ++
    verifierAcceptingRowSegmentFrames W
      (initialBlankCellTargetForms W.machine.tm k)
      (cells + Polynomial.C width)
      (verifierInitialFalseWirePolynomial W)
      (Polynomial.C (6 * width)) (Polynomial.C width) 0
      (verifierAcceptingHeightTailPolynomial W) input

def verifierAcceptingStackCompiledFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (hmember : verifierAcceptingSymbol W ∈
      reachableAlphabet W.machine.tm W.machine.tm.k₁)
    (k : W.machine.tm.K) (input : List Γ) : List AffineEqFinPairFrame :=
  if _hk : k = W.machine.tm.k₁ then
    verifierAcceptingOutputStackCompiledFrames W hmember input
  else
    verifierAcceptingEmptyStackCompiledFrames W k input

def verifierAcceptingStackFamilyCompiledFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (hmember : verifierAcceptingSymbol W ∈
      reachableAlphabet W.machine.tm W.machine.tm.k₁)
    (input : List Γ) : List AffineEqFinPairFrame :=
  (arithmeticRuntimeStackSourceIndices W.machine.tm).flatMap fun index =>
    verifierAcceptingStackCompiledFrames W hmember
      ((arithmeticStackEquiv W.machine.tm).symm index) input

def verifierAcceptingBoundaryCompiledFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (hmember : verifierAcceptingSymbol W ∈
      reachableAlphabet W.machine.tm W.machine.tm.k₁)
    (input : List Γ) : List AffineEqFinPairFrame :=
  verifierAcceptingControlCompiledFrames W input ++
    verifierAcceptingStackFamilyCompiledFrames W hmember input

private theorem accepting_encodeAffineEqFinFrames_flatMap {α : Type}
    (items : List α) (frames : α → List AffineEqFinPairFrame) :
    encodeAffineEqFinFrames (items.flatMap frames) =
      items.flatMap fun item => encodeAffineEqFinFrames (frames item) := by
  induction items with
  | nil => rfl
  | cons item rest ih =>
      simp only [List.flatMap_cons]
      unfold encodeAffineEqFinFrames at ih ⊢
      rw [List.flatMap_append, ih]

/-- The concrete positive source target is the serialization of its explicit
compiled frame family. -/
theorem verifierAcceptingBoundaryInputTarget_eq_compiledFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (hmember : verifierAcceptingSymbol W ∈
      reachableAlphabet W.machine.tm W.machine.tm.k₁)
    (input : List Γ) :
    verifierAcceptingBoundaryInputTarget W hmember input =
      encodeAffineEqFinFrames
        (verifierAcceptingBoundaryCompiledFrames W hmember input) := by
  unfold verifierAcceptingBoundaryInputTarget
    verifierAcceptingControlInput verifierAcceptingStackFamilyInput
    verifierAcceptingBoundaryCompiledFrames
    verifierAcceptingControlCompiledFrames
    verifierAcceptingStackFamilyCompiledFrames
    verifierAcceptingRowSegmentInput verifierAcceptingRowSegmentFrames
  rw [show encodeAffineEqFinFrames
      (dynamicFirstAffineEqFinRowFrames
          (acceptingControlTargetForms W.machine.tm)
          (verifierAcceptingPrevious W 0)
          (verifierLastRowStartPolynomial W + 0)
          (verifierInitialFalseWirePolynomial W) 0 0 0 1 input ++
        (arithmeticRuntimeStackSourceIndices W.machine.tm).flatMap fun index =>
          verifierAcceptingStackCompiledFrames W hmember
            ((arithmeticStackEquiv W.machine.tm).symm index) input) =
      encodeAffineEqFinFrames
          (dynamicFirstAffineEqFinRowFrames
            (acceptingControlTargetForms W.machine.tm)
            (verifierAcceptingPrevious W 0)
            (verifierLastRowStartPolynomial W + 0)
            (verifierInitialFalseWirePolynomial W) 0 0 0 1 input) ++
        encodeAffineEqFinFrames
          ((arithmeticRuntimeStackSourceIndices W.machine.tm).flatMap
            fun index => verifierAcceptingStackCompiledFrames W hmember
              ((arithmeticStackEquiv W.machine.tm).symm index) input) by
        simp [encodeAffineEqFinFrames]]
  rw [accepting_encodeAffineEqFinFrames_flatMap]
  congr 1
  apply List.flatMap_congr
  intro index hindex
  let k := (arithmeticStackEquiv W.machine.tm).symm index
  change verifierAcceptingStackInput W hmember k input =
    encodeAffineEqFinFrames
      (verifierAcceptingStackCompiledFrames W hmember k input)
  by_cases hk : k = W.machine.tm.k₁
  · simp [verifierAcceptingStackInput,
      verifierAcceptingStackCompiledFrames, hk,
      verifierAcceptingOutputStackInput,
      verifierAcceptingOutputStackCompiledFrames,
      verifierAcceptingSegmentInput, verifierAcceptingSegmentFrames,
      verifierAcceptingRowSegmentInput,
      verifierAcceptingRowSegmentFrames,
      dynamicFirstAffineEqFinInput,
      dynamicFirstAffineEqFinRowInput,
      encodeAffineEqFinFrames, List.append_assoc]
  · simp [verifierAcceptingStackInput,
      verifierAcceptingStackCompiledFrames, hk,
      verifierAcceptingEmptyStackInput,
      verifierAcceptingEmptyStackCompiledFrames,
      verifierAcceptingSegmentInput, verifierAcceptingSegmentFrames,
      verifierAcceptingRowSegmentInput,
      verifierAcceptingRowSegmentFrames,
      dynamicFirstAffineEqFinInput,
      dynamicFirstAffineEqFinRowInput,
      encodeAffineEqFinFrames, List.append_assoc]

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