Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_6986319a00044f1dceca69fb

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_f6f74da97290e2f5f315b857
import Definitions.Def_PricingWithTips3DM_684dcbeca245b170a207f743
import Definitions.Def_PricingWithTips3DM_d7d7179fdd7cff121a19a828
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Seed-row adapters for statement descriptor fragments

The affine head compiler and recursive branch descriptor compiler predate the
uniform seed-row interface.  This module exposes both through that interface,
without changing either underlying target or machine.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- A fixed affine form table as a uniform one-row-per-transition-seed
source.  Empty tables are supported and therefore cover `halt`. -/
noncomputable def verifierTransitionAffineFormSeedRowSource
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (forms : List AffineUnaryTripleForm) :
    VerifierTransitionSeedRowSource W where
  row seed := encodeUnaryFrame
    (affineUnaryTripleMap forms (transitionTailAffineSeed seed))
  family := verifierTransitionAffineFormDescriptorFamily W forms
  rows_eq _ := rfl
  computableInPolyTime :=
    verifierTransitionAffineFormDescriptorFamilyTotal_computableInPolyTime W
      forms

/-- The numeric descriptor of one fixed recursive branch as a uniform
one-row-per-transition-seed source. -/
noncomputable def verifierTransitionRecursiveBranchWidthSeedRowSource
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    VerifierTransitionSeedRowSource W where
  row seed := encodeUnaryFrame
    [cfgBitCount W.machine.tm (workHeight W.machine.tm seed.height)]
  family := verifierTransitionAffineFormDescriptorFamily W
    [transitionDispatchHeightForm
      ((transitionCfgBitAffine W.machine.tm).shiftInput
        (maxPushesPerStep W.machine.tm))]
  rows_eq input := by
    unfold verifierTransitionAffineFormDescriptorFamily
    apply List.map_congr_left
    intro seed hseed
    congr 1
    simp [affineUnaryTripleMap, transitionDispatchHeightForm_value,
      TransitionAffineNat.eval_shiftInput, workHeight]
  computableInPolyTime :=
    verifierTransitionAffineFormDescriptorFamilyTotal_computableInPolyTime W
      [transitionDispatchHeightForm
        ((transitionCfgBitAffine W.machine.tm).shiftInput
          (maxPushesPerStep W.machine.tm))]

/-- A branch descriptor carries its common row width before the selector and
three width-dependent channels.  This makes the variable-size packet
self-delimiting for a downstream fixed controller. -/
def transitionStmtRecursiveBranchLengthPrefixedNumericDescriptorRow
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (view : TransitionDispatchMuxInvocationView) : List UnaryFrameSym :=
  encodeUnaryFrame [cfgBitCount tm (workHeight tm seed.height)] ++
    view.numericDescriptorRow

/-- The numeric descriptor of one fixed recursive branch as a uniform
one-row-per-transition-seed source. -/
noncomputable def verifierTransitionRecursiveBranchSeedRowSource
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (labelOffset : TransitionAffineNat)
    (context : TransitionStmtAffineContext W.machine.tm)
    (test : W.machine.tm.σ → Bool)
    (whenTrue whenFalse : _root_.Turing.TM2.Stmt W.machine.tm.Γ
      W.machine.tm.Λ W.machine.tm.σ)
    (hsupport : ∀ k,
      stmtPushSet W.machine.tm (.branch test whenTrue whenFalse) k ⊆
        reachableAlphabet W.machine.tm k)
    (htrueBounds :
      (transitionStmtRecursivePlan W.machine.tm labelOffset
        (transitionStmtBranchTrueContext W.machine.tm context test) whenTrue
        (transitionStmtBranchTrueSupport W.machine.tm test whenTrue whenFalse
          hsupport)).UniformLinearRouteBounds W labelOffset)
    (hfalseBounds :
      (transitionStmtRecursivePlan W.machine.tm labelOffset
        (transitionStmtBranchFalseContext W.machine.tm context test whenTrue)
        whenFalse
        (transitionStmtBranchFalseSupport W.machine.tm test whenTrue whenFalse
          hsupport)).UniformLinearRouteBounds W labelOffset) :
    VerifierTransitionSeedRowSource W :=
  let width := verifierTransitionRecursiveBranchWidthSeedRowSource W
  let body : VerifierTransitionSeedRowSource W :=
    { row := fun seed =>
        (transitionStmtRecursiveBranchMuxInvocationView W.machine.tm seed
          labelOffset context test whenTrue whenFalse
            hsupport).numericDescriptorRow
      family := verifierTransitionRecursiveBranchDescriptorFamily W
        labelOffset context test whenTrue whenFalse hsupport
      rows_eq := fun input => by
        rw [verifierTransitionRecursiveBranchDescriptorFamily_rows]
        unfold verifierTransitionRecursiveBranchViews
        rw [List.map_map]
        apply List.map_congr_left
        intro seed hseed
        rfl
      computableInPolyTime :=
        verifierTransitionRecursiveBranchDescriptorFamily_computableInPolyTime
          W labelOffset context test whenTrue whenFalse hsupport htrueBounds
            hfalseBounds }
  width.append body

/-- Exact self-delimiting row produced by the recursive branch adapter. -/
theorem verifierTransitionRecursiveBranchSeedRowSource_row
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (seed : TransitionRowSeed)
    (labelOffset : TransitionAffineNat)
    (context : TransitionStmtAffineContext W.machine.tm)
    (test : W.machine.tm.σ → Bool)
    (whenTrue whenFalse : _root_.Turing.TM2.Stmt W.machine.tm.Γ
      W.machine.tm.Λ W.machine.tm.σ)
    (hsupport : ∀ k,
      stmtPushSet W.machine.tm (.branch test whenTrue whenFalse) k ⊆
        reachableAlphabet W.machine.tm k)
    (htrueBounds :
      (transitionStmtRecursivePlan W.machine.tm labelOffset
        (transitionStmtBranchTrueContext W.machine.tm context test) whenTrue
        (transitionStmtBranchTrueSupport W.machine.tm test whenTrue whenFalse
          hsupport)).UniformLinearRouteBounds W labelOffset)
    (hfalseBounds :
      (transitionStmtRecursivePlan W.machine.tm labelOffset
        (transitionStmtBranchFalseContext W.machine.tm context test whenTrue)
        whenFalse
        (transitionStmtBranchFalseSupport W.machine.tm test whenTrue whenFalse
          hsupport)).UniformLinearRouteBounds W labelOffset) :
    (verifierTransitionRecursiveBranchSeedRowSource W labelOffset context
      test whenTrue whenFalse hsupport htrueBounds hfalseBounds).row seed =
      transitionStmtRecursiveBranchLengthPrefixedNumericDescriptorRow
        W.machine.tm seed
        (transitionStmtRecursiveBranchMuxInvocationView W.machine.tm seed
          labelOffset context test whenTrue whenFalse hsupport) := rfl

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