Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_2b2043d97c6219d5e9e3ac58

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

/-!
# Fixed affine table for all terminal true-arm prefixes

The unified true-arm layout contains both branch-ending and terminal-ending
program labels.  This module filters that fixed layout table without changing
label order, retaining exactly the affine halted/label/state prefix of every
terminal entry.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- Fixed forms contributed by one normalized true-arm entry.  Branch rows
have no terminal prefix; terminal rows contribute their complete fixed prefix
table. -/
noncomputable def
    TransitionDispatchTrueArmNormalizedLayout.terminalPrefixForms
    (tm : _root_.Turing.FinTM2) :
    TransitionDispatchTrueArmNormalizedLayout tm →
      List AffineUnaryTripleForm
  | .branch _ _ _ _ => []
  | .terminal labelOffset _ rowLayout _ =>
      transitionStmtTerminalPrefixForms tm labelOffset rowLayout

/-- Semantic prefix values selected by the same fixed terminal mask. -/
def TransitionDispatchTrueArmNormalizedLayout.terminalPrefixValues
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    TransitionDispatchTrueArmNormalizedLayout tm → List Nat
  | .branch _ _ _ _ => []
  | .terminal labelOffset _ rowLayout _ =>
      rowLayout.prefixValues tm
        (seed.start + labelOffset.eval seed.height)
        (workHeight tm seed.height) seed.start (seed.start + 1)
        (arithmeticWidenedCfgWires tm seed.height seed.start seed.rowBase)

/-- Each entry's fixed form table evaluates exactly to its selected semantic
prefix values. -/
theorem
    TransitionDispatchTrueArmNormalizedLayout.terminalPrefixForms_value
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (layout : TransitionDispatchTrueArmNormalizedLayout tm) :
    affineUnaryTripleMap (layout.terminalPrefixForms tm)
        (transitionTailAffineSeed seed) =
      layout.terminalPrefixValues tm seed := by
  cases layout with
  | branch labelOffset label branchOffset hbranch => rfl
  | terminal labelOffset label rowLayout hlayout =>
      exact transitionStmtTerminalPrefixForms_value tm seed labelOffset
        rowLayout

/-- Complete verifier-fixed affine form table for all terminal entries, in
original program-label order. -/
noncomputable def transitionDispatchTerminalPrefixForms
    (tm : _root_.Turing.FinTM2) : List AffineUnaryTripleForm :=
  (transitionDispatchTrueArmNormalizedLayouts tm).flatMap
    (TransitionDispatchTrueArmNormalizedLayout.terminalPrefixForms tm)

/-- Complete semantic terminal-prefix value stream for one transition row. -/
def transitionDispatchTerminalPrefixValues
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) : List Nat :=
  (transitionDispatchTrueArmNormalizedLayouts tm).flatMap
    (TransitionDispatchTrueArmNormalizedLayout.terminalPrefixValues tm seed)

/-- Evaluating the complete fixed table yields exactly all terminal prefixes
for one transition row. -/
theorem transitionDispatchTerminalPrefixForms_value
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    affineUnaryTripleMap (transitionDispatchTerminalPrefixForms tm)
        (transitionTailAffineSeed seed) =
      transitionDispatchTerminalPrefixValues tm seed := by
  unfold transitionDispatchTerminalPrefixForms
    transitionDispatchTerminalPrefixValues affineUnaryTripleMap
  rw [List.map_flatMap]
  apply List.flatMap_congr
  intro layout hlayout
  exact layout.terminalPrefixForms_value tm seed

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