Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_29fe1ade4792db459eadc3a6

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_859f44e236337f5926ded6d7
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Linear prefixes ending in a terminal branch

Real TM2 statements need not begin with a branch: state and stack operations
may precede it.  This module walks that fixed linear spine, records its affine
phases and exact continuation context, and then attaches the verified
terminal-arm branch plan at the leaf.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open _root_.Turing.TM2 _root_.Turing.TM2.Stmt

/-- A linear affine prefix together with its final branch whose two arms are
branch-free. -/
structure TransitionStmtPrefixTerminalBranchPlan
    (tm : _root_.Turing.FinTM2) where
  prefixForms : List TransitionAffineStmtPhaseForm
  branchContext : TransitionStmtAffineContext tm
  test : tm.σ → Bool
  whenTrue : _root_.Turing.TM2.Stmt tm.Γ tm.Λ tm.σ
  whenFalse : _root_.Turing.TM2.Stmt tm.Γ tm.Λ tm.σ
  branchSupport : ∀ k,
    stmtPushSet tm (.branch test whenTrue whenFalse) k ⊆
      reachableAlphabet tm k
  branchPlan : TransitionStmtTerminalBranchPlan tm

/-- All fixed-width phases before the height-dependent final mux. -/
def TransitionStmtPrefixTerminalBranchPlan.fixedPhaseForms
    (tm : _root_.Turing.FinTM2) (labelOffset : TransitionAffineNat)
    (plan : TransitionStmtPrefixTerminalBranchPlan tm) :
    List TransitionAffineStmtPhaseForm :=
  plan.prefixForms ++
    plan.branchPlan.fixedPhaseForms tm labelOffset plan.branchContext
      plan.test plan.whenTrue plan.whenFalse plan.branchSupport

/-- Static shape predicate recognized by this first branch layer. -/
def transitionStmtEndsInTerminalBranch
    (tm : _root_.Turing.FinTM2) :
    _root_.Turing.TM2.Stmt tm.Γ tm.Λ tm.σ → Prop
  | halt => False
  | goto _ => False
  | load _ continuation => transitionStmtEndsInTerminalBranch tm continuation
  | push _ _ continuation => transitionStmtEndsInTerminalBranch tm continuation
  | peek _ _ continuation => transitionStmtEndsInTerminalBranch tm continuation
  | pop _ _ continuation => transitionStmtEndsInTerminalBranch tm continuation
  | branch _ whenTrue whenFalse =>
      (transitionStmtTerminalLayout tm whenTrue).isSome ∧
        (transitionStmtTerminalLayout tm whenFalse).isSome

/-- Compile a fixed linear prefix and its final branch with branch-free arms. -/
noncomputable def transitionStmtPrefixTerminalBranchPlan
    (tm : _root_.Turing.FinTM2) (labelOffset : TransitionAffineNat) :
    (context : TransitionStmtAffineContext tm) →
    (q : _root_.Turing.TM2.Stmt tm.Γ tm.Λ tm.σ) →
    (∀ k, stmtPushSet tm q k ⊆ reachableAlphabet tm k) →
      Option (TransitionStmtPrefixTerminalBranchPlan tm)
  | _, halt, _ => none
  | _, goto _, _ => none
  | context, load update continuation, hsupport =>
      let hcontinuation : ∀ k,
          stmtPushSet tm continuation k ⊆ reachableAlphabet tm k := by
        simpa [stmtPushSet] using hsupport
      (transitionStmtPrefixTerminalBranchPlan tm labelOffset
        (context.afterLoad tm update) continuation hcontinuation).map
          (fun plan => { plan with
            prefixForms :=
              (transitionStmtContextHeadPhaseForm tm labelOffset context
                (.load update continuation) hsupport).toList ++
                plan.prefixForms })
  | context, push k emit continuation, hsupport =>
      let hcontinuation : ∀ j,
          stmtPushSet tm continuation j ⊆ reachableAlphabet tm j := by
        intro j symbol hsymbol
        apply hsupport j
        simp only [stmtPushSet]
        exact Finset.mem_union_right _ hsymbol
      let symbolAt : Fin (stateCount tm) → SupportedSymbol tm k := fun code =>
        ⟨emit ((stateEquivFin tm).symm code), by
          apply hsupport k
          simp [stmtPushSet]⟩
      let table := fun code => encodeSupportedSymbol (symbolAt code)
      (transitionStmtPrefixTerminalBranchPlan tm labelOffset
        (context.afterPush tm k table) continuation hcontinuation).map
          (fun plan => { plan with
            prefixForms :=
              (transitionStmtContextHeadPhaseForm tm labelOffset context
                (.push k emit continuation) hsupport).toList ++
                plan.prefixForms })
  | context, peek k update continuation, hsupport =>
      let hcontinuation : ∀ j,
          stmtPushSet tm continuation j ⊆ reachableAlphabet tm j := by
        simpa [stmtPushSet] using hsupport
      (transitionStmtPrefixTerminalBranchPlan tm labelOffset
        (context.afterPeek tm k update) continuation hcontinuation).map
          (fun plan => { plan with
            prefixForms :=
              (transitionStmtContextHeadPhaseForm tm labelOffset context
                (.peek k update continuation) hsupport).toList ++
                plan.prefixForms })
  | context, pop k update continuation, hsupport =>
      let hcontinuation : ∀ j,
          stmtPushSet tm continuation j ⊆ reachableAlphabet tm j := by
        simpa [stmtPushSet] using hsupport
      (transitionStmtPrefixTerminalBranchPlan tm labelOffset
        (context.afterPop tm k update) continuation hcontinuation).map
          (fun plan => { plan with
            prefixForms := transitionStmtContextPopPhaseForms tm labelOffset
              context k update ++ plan.prefixForms })
  | context, branch test whenTrue whenFalse, hsupport =>
      (transitionStmtTerminalBranchPlan tm labelOffset context test whenTrue
        whenFalse hsupport).map fun branchPlan =>
          { prefixForms := []
            branchContext := context
            test := test
            whenTrue := whenTrue
            whenFalse := whenFalse
            branchSupport := hsupport
            branchPlan := branchPlan }

/-- The prefix compiler succeeds exactly on a linear spine ending in a branch
whose two arms are branch-free. -/
theorem transitionStmtPrefixTerminalBranchPlan_isSome_iff
    (tm : _root_.Turing.FinTM2) (labelOffset : TransitionAffineNat)
    (context : TransitionStmtAffineContext tm)
    (q : _root_.Turing.TM2.Stmt tm.Γ tm.Λ tm.σ)
    (hsupport : ∀ k, stmtPushSet tm q k ⊆ reachableAlphabet tm k) :
    (transitionStmtPrefixTerminalBranchPlan tm labelOffset context q
      hsupport).isSome ↔ transitionStmtEndsInTerminalBranch tm q := by
  induction q generalizing context with
  | halt => simp [transitionStmtPrefixTerminalBranchPlan,
      transitionStmtEndsInTerminalBranch]
  | goto jump => simp [transitionStmtPrefixTerminalBranchPlan,
      transitionStmtEndsInTerminalBranch]
  | load update continuation ih =>
      simp [transitionStmtPrefixTerminalBranchPlan,
        transitionStmtEndsInTerminalBranch, ih]
  | push k emit continuation ih =>
      simp [transitionStmtPrefixTerminalBranchPlan,
        transitionStmtEndsInTerminalBranch, ih]
  | peek k update continuation ih =>
      simp [transitionStmtPrefixTerminalBranchPlan,
        transitionStmtEndsInTerminalBranch, ih]
  | pop k update continuation ih =>
      simp [transitionStmtPrefixTerminalBranchPlan,
        transitionStmtEndsInTerminalBranch, ih]
  | branch test whenTrue whenFalse ihTrue ihFalse =>
      simpa [transitionStmtPrefixTerminalBranchPlan,
        transitionStmtEndsInTerminalBranch] using
        transitionStmtTerminalBranchPlan_isSome_iff tm labelOffset context
          test whenTrue whenFalse hsupport

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