Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_85682be83e308fd907f0b5ea

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

/-!
# Complete terminal-row compiler from compact affine spans

The affine terminal prefix and all normalized stack blocks are placed in one
fixed segment group.  The resulting concrete polynomial-time machine emits a
complete terminal true-arm row per verifier transition seed, in canonical
machine-stack order.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- All normalized stack segment tables in canonical machine-stack order. -/
noncomputable def TransitionStmtTerminalRowLayout.stackAffineSpanSegments
    (tm : _root_.Turing.FinTM2) (labelOffset : TransitionAffineNat)
    (layout : TransitionStmtTerminalRowLayout tm) :
    List TransitionWidenedFallbackSegment :=
  (arithmeticRuntimeStackSourceIndices tm).flatMap fun position =>
    let k := (arithmeticStackEquiv tm).symm position
    transitionStackAffineSpanBlockSegments tm k
      (layout.stackAffineSpanRoute tm k labelOffset)

/-- Prefix-drop tables corresponding to every normalized stack segment table.
-/
def TransitionStmtTerminalRowLayout.stackAffineSpanDropAmounts
    (tm : _root_.Turing.FinTM2) (labelOffset : TransitionAffineNat)
    (layout : TransitionStmtTerminalRowLayout tm) : List Nat :=
  (arithmeticRuntimeStackSourceIndices tm).flatMap fun position =>
    let k := (arithmeticStackEquiv tm).symm position
    transitionStackAffineSpanBlockDropAmounts tm k
      (layout.stackAffineSpanRoute tm k labelOffset)

theorem TransitionStmtTerminalRowLayout.stackAffineSpanDropAmounts_length
    (tm : _root_.Turing.FinTM2) (labelOffset : TransitionAffineNat)
    (layout : TransitionStmtTerminalRowLayout tm) :
    (layout.stackAffineSpanDropAmounts tm labelOffset).length =
      (layout.stackAffineSpanSegments tm labelOffset).length := by
  unfold TransitionStmtTerminalRowLayout.stackAffineSpanDropAmounts
    TransitionStmtTerminalRowLayout.stackAffineSpanSegments
  induction arithmeticRuntimeStackSourceIndices tm with
  | nil => rfl
  | cons position positions ih =>
      simp only [List.flatMap_cons, List.length_append]
      rw [transitionStackAffineSpanBlockDropAmounts_length, ih]

/-- Complete affine segment table for one terminal true-arm row. -/
noncomputable def TransitionStmtTerminalRowLayout.terminalAffineSpanSegments
    (tm : _root_.Turing.FinTM2) (labelOffset : TransitionAffineNat)
    (layout : TransitionStmtTerminalRowLayout tm) :
    List TransitionWidenedFallbackSegment :=
  transitionStackAffineSpanConstantSegments
      (transitionStmtTerminalPrefixForms tm labelOffset layout) ++
    layout.stackAffineSpanSegments tm labelOffset

/-- Complete fixed prefix-drop table for one terminal true-arm row. -/
def TransitionStmtTerminalRowLayout.terminalAffineSpanDropAmounts
    (tm : _root_.Turing.FinTM2) (labelOffset : TransitionAffineNat)
    (layout : TransitionStmtTerminalRowLayout tm) : List Nat :=
  List.replicate
      (transitionStmtTerminalPrefixForms tm labelOffset layout).length 0 ++
    layout.stackAffineSpanDropAmounts tm labelOffset

theorem TransitionStmtTerminalRowLayout.terminalAffineSpanDropAmounts_length
    (tm : _root_.Turing.FinTM2) (labelOffset : TransitionAffineNat)
    (layout : TransitionStmtTerminalRowLayout tm) :
    (layout.terminalAffineSpanDropAmounts tm labelOffset).length =
      (layout.terminalAffineSpanSegments tm labelOffset).length := by
  simp only [TransitionStmtTerminalRowLayout.terminalAffineSpanDropAmounts,
    TransitionStmtTerminalRowLayout.terminalAffineSpanSegments,
    List.length_append, List.length_replicate,
    transitionStackAffineSpanConstantSegments_length]
  rw [layout.stackAffineSpanDropAmounts_length]

theorem TransitionStmtTerminalRowLayout.terminalAffineSpanDropAmounts_nonempty
    (tm : _root_.Turing.FinTM2) (labelOffset : TransitionAffineNat)
    (layout : TransitionStmtTerminalRowLayout tm) :
    0 < (layout.terminalAffineSpanDropAmounts tm labelOffset).length := by
  unfold TransitionStmtTerminalRowLayout.terminalAffineSpanDropAmounts
    transitionStmtTerminalPrefixForms
  simp

/-- All normalized stack segment groups evaluate to the established terminal
stack descriptor routes. -/
theorem TransitionStmtTerminalRowLayout.stackAffineSpanSegments_values
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) (seed : TransitionRowSeed)
    (hseed : seed ∈ verifierTransitionRowSeeds W input)
    (label : W.machine.tm.Λ) (labelOffset : TransitionAffineNat)
    (layout : TransitionStmtTerminalRowLayout W.machine.tm)
    (hlayout : transitionStmtTerminalRowLayout W.machine.tm
      (W.machine.tm.m label)
      (stmtPushSet_program_subset W.machine.tm label) = some layout) :
    unaryFrameFixedGroupPrefixDropValues
        (layout.stackAffineSpanDropAmounts W.machine.tm labelOffset)
        (transitionAffineSegmentValueRows seed
          (layout.stackAffineSpanSegments W.machine.tm labelOffset)) =
      (layout.stackDescriptorRouteValues W.machine.tm
        (seed.start + labelOffset.eval seed.height) seed).flatten := by
  unfold TransitionStmtTerminalRowLayout.stackAffineSpanDropAmounts
    TransitionStmtTerminalRowLayout.stackAffineSpanSegments
    TransitionStmtTerminalRowLayout.stackDescriptorRouteValues
    transitionAffineSegmentValueRows
  induction arithmeticRuntimeStackSourceIndices W.machine.tm with
  | nil => rfl
  | cons position positions ih =>
      simp only [List.flatMap_cons, List.map_append, List.map_cons,
        List.flatten_cons]
      rw [unaryFrameFixedGroupPrefixDropValues_append]
      · let k := (arithmeticStackEquiv W.machine.tm).symm position
        have hblock := layout.stackAffineSpanBlockSegments_values W input seed
          hseed label labelOffset hlayout k
        unfold transitionAffineSegmentValueRows at hblock
        rw [hblock]
        rw [layout.stackAffineSpanRoute_eval W input seed hseed label
          labelOffset hlayout k]
        rw [ih]
      · rw [List.length_map,
          transitionStackAffineSpanBlockDropAmounts_length]

/-- The whole terminal segment group evaluates exactly to the already verified
descriptor-derived terminal row. -/
theorem TransitionStmtTerminalRowLayout.terminalAffineSpanSegments_values
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) (seed : TransitionRowSeed)
    (hseed : seed ∈ verifierTransitionRowSeeds W input)
    (label : W.machine.tm.Λ) (labelOffset : TransitionAffineNat)
    (layout : TransitionStmtTerminalRowLayout W.machine.tm)
    (hlayout : transitionStmtTerminalRowLayout W.machine.tm
      (W.machine.tm.m label)
      (stmtPushSet_program_subset W.machine.tm label) = some layout) :
    unaryFrameFixedGroupPrefixDropValues
        (layout.terminalAffineSpanDropAmounts W.machine.tm labelOffset)
        (transitionAffineSegmentValueRows seed
          (layout.terminalAffineSpanSegments W.machine.tm labelOffset)) =
      (TransitionDispatchTrueArmNormalizedLayout.terminal labelOffset label
        layout hlayout).terminalRowDescriptorRoute W.machine.tm seed := by
  unfold TransitionStmtTerminalRowLayout.terminalAffineSpanDropAmounts
    TransitionStmtTerminalRowLayout.terminalAffineSpanSegments
    transitionAffineSegmentValueRows
  rw [List.map_append]
  rw [unaryFrameFixedGroupPrefixDropValues_append]
  · have hprefix := transitionStackAffineSpanConstantSegments_zeroDrop_values
      seed (transitionStmtTerminalPrefixForms W.machine.tm labelOffset layout)
    unfold transitionAffineSegmentValueRows at hprefix
    rw [hprefix]
    have hstacks := layout.stackAffineSpanSegments_values W input seed hseed
      label labelOffset hlayout
    unfold transitionAffineSegmentValueRows at hstacks
    rw [hstacks]
    simp only [
      TransitionDispatchTrueArmNormalizedLayout.terminalRowDescriptorRoute]
  · simp [transitionStackAffineSpanConstantSegments_length]

/-- Raw-input generated marked rows for one fixed terminal layout. -/
noncomputable def verifierTransitionTerminalAffineSpanFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (labelOffset : TransitionAffineNat)
    (layout : TransitionStmtTerminalRowLayout W.machine.tm)
    (input : List Γ) : List UnaryFrameSym :=
  rewriteUnaryFrameFixedGroupPrefixDrop
    (layout.terminalAffineSpanDropAmounts W.machine.tm labelOffset)
    (layout.terminalAffineSpanDropAmounts_nonempty W.machine.tm labelOffset)
    (verifierTransitionAffineSegmentRowFrames W
      (layout.terminalAffineSpanSegments W.machine.tm labelOffset) input)

/-- A concrete polynomial-time TM2 emits every complete row of one fixed
terminal layout directly from the verifier input. -/
noncomputable def
    verifierTransitionTerminalAffineSpanFrames_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (labelOffset : TransitionAffineNat)
    (layout : TransitionStmtTerminalRowLayout W.machine.tm) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierTransitionTerminalAffineSpanFrames W labelOffset layout) := by
  let source := verifierTransitionAffineSegmentRowFrames_computableInPolyTime W
    (layout.terminalAffineSpanSegments W.machine.tm labelOffset)
  let rewritten :=
    _root_.Turing.TM2Comp.TM2ComputableInPolyTime.comp_scratch source
      (unaryFrameFixedGroupPrefixDrop_computableInPolyTime
        (layout.terminalAffineSpanDropAmounts W.machine.tm labelOffset)
        (layout.terminalAffineSpanDropAmounts_nonempty
          W.machine.tm labelOffset))
  change _root_.Turing.TM2ComputableInPolyTime id id
    (fun input => rewriteUnaryFrameFixedGroupPrefixDrop
      (layout.terminalAffineSpanDropAmounts W.machine.tm labelOffset)
      (layout.terminalAffineSpanDropAmounts_nonempty W.machine.tm labelOffset)
      (verifierTransitionAffineSegmentRowFrames W
        (layout.terminalAffineSpanSegments W.machine.tm labelOffset) input))
  simpa [Function.comp_def] using Classical.choice rewritten

/-- Exact semantic output of the fixed terminal-layout source machine. -/
theorem TransitionStmtTerminalRowLayout.verifierTerminalAffineSpanFrames_eq
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) (label : W.machine.tm.Λ)
    (labelOffset : TransitionAffineNat)
    (layout : TransitionStmtTerminalRowLayout W.machine.tm)
    (hlayout : transitionStmtTerminalRowLayout W.machine.tm
      (W.machine.tm.m label)
      (stmtPushSet_program_subset W.machine.tm label) = some layout) :
    verifierTransitionTerminalAffineSpanFrames W labelOffset layout input =
      (verifierTransitionRowSeeds W input).flatMap fun seed =>
        encodeUnaryFrame
            ((TransitionDispatchTrueArmNormalizedLayout.terminal labelOffset
              label layout hlayout).terminalRowValueRoute W.machine.tm seed) ++
          [.frameEnd] := by
  unfold verifierTransitionTerminalAffineSpanFrames
  rw [verifierTransitionAffineSegmentRowFrames_eq]
  rw [rewriteUnaryFrameFixedGroupPrefixDrop_groups]
  · unfold encodeUnaryFrameFixedGroupPrefixDropOutput
    rw [List.flatMap_map]
    apply List.flatMap_congr
    intro seed hseed
    rw [layout.terminalAffineSpanSegments_values W input seed hseed label
      labelOffset hlayout]
    rw [TransitionDispatchTrueArmNormalizedLayout.terminalRowDescriptorRoute_eq]
  · intro group hgroup
    rw [List.mem_map] at hgroup
    rcases hgroup with ⟨seed, hseed, rfl⟩
    unfold transitionAffineSegmentValueRows
    rw [List.length_map]
    exact (layout.terminalAffineSpanDropAmounts_length W.machine.tm
      labelOffset).symm

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