Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_c67ece6c69d5b0ef567eae8d

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

/-!
# Structured flattening of transition configuration rows

This file factors the canonical flat row into its fixed status/state prefix
and one block per verifier stack.  It is intentionally independent of any
particular statement action or TM2 controller.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

/-- Halted, label, and state wires in canonical prefix order. -/
def transitionCfgPrefixWireValues
    (tm : _root_.Turing.FinTM2) (height : Nat)
    (source : CfgWires tm height) : List Nat :=
  (transitionEqPrefixSlots tm height).map source

/-- One canonical flat wire block for every stack in fixed-machine order. -/
def transitionCfgStackWireBlocks
    (tm : _root_.Turing.FinTM2) (height : Nat)
    (source : CfgWires tm height) : List (List Nat) :=
  (arithmeticRuntimeStackSourceIndices tm).map fun position =>
    transitionStackWireValues
      (source.stack ((arithmeticStackEquiv tm).symm position))

/-- Structured row flattening: fixed prefix followed by all stack blocks. -/
def transitionCfgStructuredWireValues
    (tm : _root_.Turing.FinTM2) (height : Nat)
    (source : CfgWires tm height) : List Nat :=
  transitionCfgPrefixWireValues tm height source ++
    (transitionCfgStackWireBlocks tm height source).flatten

/-- The structured factorization is literally the canonical coordinate-order
row used by every transition controller. -/
theorem transitionCfgStructuredWireValues_eq_canonical
    (tm : _root_.Turing.FinTM2) (height : Nat)
    (source : CfgWires tm height) :
    transitionCfgStructuredWireValues tm height source =
      transitionCfgWireValues tm height source := by
  have hstructured :
      transitionCfgStructuredWireValues tm height source =
        (transitionEqPublicSlots tm height).map source := by
    unfold transitionCfgStructuredWireValues
      transitionCfgPrefixWireValues transitionCfgStackWireBlocks
      transitionEqPublicSlots
    rw [List.map_append, List.map_flatten, List.map_map]
    congr 1
    apply congrArg List.flatten
    apply List.map_congr_left
    intro position hposition
    exact transitionStackWireValues_eq_slot_map tm height source
      ((arithmeticStackEquiv tm).symm position)
  rw [hstructured, transitionEqPublicSlots_eq_canonical]
  unfold transitionCfgWireValues
  rw [List.map_ofFn]
  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