Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_54e189382b52321285018da7

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

/-!
# Affine prefix forms of normalized statement terminals

The halted, label, and state coordinates of a normalized branch arm are fixed
affine functions of the enclosing transition seed.  Stack coordinates remain
in the context's compact route and are joined in the following mux-source
layer.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- Affine forms of the terminal label family at the final context start. -/
noncomputable def TransitionStmtLinearResult.labelForms
    (tm : _root_.Turing.FinTM2) (labelOffset : TransitionAffineNat)
    (result : TransitionStmtLinearResult tm) :
    List AffineUnaryTripleForm :=
  match result.terminal with
  | .halt =>
      List.ofFn fun target : Fin (labelCount tm + 1) =>
        if target = encodeLabel tm (none : Option tm.Λ) then
          transitionAbsoluteStartForm (TransitionAffineNat.const 1)
        else transitionAbsoluteStartForm (TransitionAffineNat.const 0)
  | .goto jump =>
      List.ofFn fun target : Fin (labelCount tm + 1) =>
        transitionAffineFormAddConst
          (result.context.startForm tm labelOffset)
          (oneHotMapWireOffset (stmtLabelTable tm jump) target)

/-- Affine forms of the final state family. -/
noncomputable def TransitionStmtLinearResult.stateForms
    (tm : _root_.Turing.FinTM2) (labelOffset : TransitionAffineNat)
    (result : TransitionStmtLinearResult tm) :
    List AffineUnaryTripleForm :=
  List.ofFn (result.context.stateForm tm labelOffset)

/-- Complete fixed-width prefix of a normalized arm output row. -/
noncomputable def TransitionStmtLinearResult.prefixForms
    (tm : _root_.Turing.FinTM2) (labelOffset : TransitionAffineNat)
    (result : TransitionStmtLinearResult tm) :
    List AffineUnaryTripleForm :=
  transitionStmtTerminalHaltedForm tm result.terminal ::
    result.labelForms tm labelOffset ++ result.stateForms tm labelOffset

/-- Runtime halted/label/state prefix of the normalized output row. -/
def TransitionStmtLinearResult.prefixValues
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (labelOffset : TransitionAffineNat)
    (result : TransitionStmtLinearResult tm) : List Nat :=
  let output := result.outputWires tm
    (seed.start + labelOffset.eval seed.height)
    (workHeight tm seed.height) seed.start (seed.start + 1)
    (arithmeticWidenedCfgWires tm seed.height seed.start seed.rowBase)
  output.halted :: List.ofFn output.label ++ List.ofFn output.state

/-- Terminal label forms evaluate to the literal normalized label wires. -/
theorem TransitionStmtLinearResult.labelForms_value
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (labelOffset : TransitionAffineNat)
    (result : TransitionStmtLinearResult tm) :
    affineUnaryTripleMap (result.labelForms tm labelOffset)
        (transitionTailAffineSeed seed) =
      let output := result.outputWires tm
        (seed.start + labelOffset.eval seed.height)
        (workHeight tm seed.height) seed.start (seed.start + 1)
        (arithmeticWidenedCfgWires tm seed.height seed.start seed.rowBase)
      List.ofFn output.label := by
  rcases result with ⟨context, terminal⟩
  cases terminal with
  | halt =>
      unfold TransitionStmtLinearResult.labelForms affineUnaryTripleMap
        TransitionStmtLinearResult.outputWires
      rw [List.map_ofFn]
      apply List.ofFn_inj.mpr
      funext target
      simp only [CfgBundle.replaceStatus_label,
        TransitionStmtTerminal.labelWires, arithmeticLabelWires]
      by_cases htarget :
          target = encodeLabel tm (none : Option tm.Λ) <;>
        simp [htarget, transitionAbsoluteStartForm_value,
          TransitionAffineNat.eval, TransitionAffineNat.const]
  | goto jump =>
      unfold TransitionStmtLinearResult.labelForms affineUnaryTripleMap
        TransitionStmtLinearResult.outputWires
      rw [List.map_ofFn]
      apply List.ofFn_inj.mpr
      funext target
      simp only [CfgBundle.replaceStatus_label,
        TransitionStmtTerminal.labelWires]
      change affineUnaryTripleFormValue
          (transitionAffineFormAddConst
            (context.startForm tm labelOffset)
            (oneHotMapWireOffset (stmtLabelTable tm jump) target))
          (transitionTailAffineSeed seed) = _
      rw [transitionAffineFormAddConst_value,
        context.startForm_value]

/-- State forms evaluate to the literal normalized state wires. -/
theorem TransitionStmtLinearResult.stateForms_value
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (labelOffset : TransitionAffineNat)
    (result : TransitionStmtLinearResult tm) :
    affineUnaryTripleMap (result.stateForms tm labelOffset)
        (transitionTailAffineSeed seed) =
      let output := result.outputWires tm
        (seed.start + labelOffset.eval seed.height)
        (workHeight tm seed.height) seed.start (seed.start + 1)
        (arithmeticWidenedCfgWires tm seed.height seed.start seed.rowBase)
      List.ofFn output.state := by
  rcases result with ⟨context, terminal⟩
  unfold TransitionStmtLinearResult.stateForms affineUnaryTripleMap
    TransitionStmtLinearResult.outputWires
  rw [List.map_ofFn]
  apply List.ofFn_inj.mpr
  funext target
  rw [CfgBundle.replaceStatus_state]
  exact context.stateForm_eq_wires tm seed labelOffset target

/-- The complete fixed prefix form table evaluates byte-for-byte to the
normalized arm's halted/label/state prefix. -/
theorem TransitionStmtLinearResult.prefixForms_value
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (labelOffset : TransitionAffineNat)
    (result : TransitionStmtLinearResult tm) :
    affineUnaryTripleMap (result.prefixForms tm labelOffset)
        (transitionTailAffineSeed seed) =
      result.prefixValues tm seed labelOffset := by
  unfold TransitionStmtLinearResult.prefixForms
    TransitionStmtLinearResult.prefixValues
  rw [show affineUnaryTripleMap
      (transitionStmtTerminalHaltedForm tm result.terminal ::
          result.labelForms tm labelOffset ++
            result.stateForms tm labelOffset)
      (transitionTailAffineSeed seed) =
        affineUnaryTripleFormValue
            (transitionStmtTerminalHaltedForm tm result.terminal)
            (transitionTailAffineSeed seed) ::
          affineUnaryTripleMap (result.labelForms tm labelOffset)
              (transitionTailAffineSeed seed) ++
            affineUnaryTripleMap (result.stateForms tm labelOffset)
              (transitionTailAffineSeed seed) by
        simp [affineUnaryTripleMap]]
  rw [transitionStmtTerminalHaltedForm_value,
    result.labelForms_value, result.stateForms_value]
  simp [TransitionStmtLinearResult.outputWires, CfgBundle.halted,
    CfgSlot.halted, CfgBundle.replaceStatus]

/-- Direct semantic bridge: the fixed prefix forms are the halted, label, and
state coordinates of the original branch-free arm output. -/
theorem transitionStmtLinearResult_prefixForms_value_output
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (hwork : 0 < workHeight tm seed.height)
    (labelOffset : TransitionAffineNat)
    (context : TransitionStmtAffineContext tm)
    (q : _root_.Turing.TM2.Stmt tm.Γ tm.Λ tm.σ)
    (hsupport : ∀ k, stmtPushSet tm q k ⊆ reachableAlphabet tm k)
    (result : TransitionStmtLinearResult tm)
    (hresult : transitionStmtLinearResult tm context q hsupport =
      some result) :
    affineUnaryTripleMap (result.prefixForms tm labelOffset)
        (transitionTailAffineSeed seed) =
      let output := transitionStmtOutputWires tm
        (workHeight tm seed.height) seed.start (seed.start + 1)
        ((seed.start + labelOffset.eval seed.height) +
          context.gateOffset.eval (workHeight tm seed.height))
        (context.rowWires tm seed labelOffset) q hsupport
      output.halted :: List.ofFn output.label ++ List.ofFn output.state := by
  rw [result.prefixForms_value]
  have houtput := transitionStmtLinearResult_outputWires tm
    (workHeight tm seed.height) hwork
    (seed.start + labelOffset.eval seed.height) seed.start (seed.start + 1)
    (arithmeticWidenedCfgWires tm seed.height seed.start seed.rowBase)
    context q hsupport result hresult
  unfold TransitionStmtLinearResult.prefixValues
  unfold TransitionStmtAffineContext.rowWires
  rw [houtput]

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