Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_827dc5cd751d1b3335bee2c0

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

/-!
# Semantics of the dispatch-mux true-arm descriptor section

The unified raw source stores every true-arm affine span as an eight-field
block: a verifier-fixed prefix-drop amount followed by one ordinary affine
triple progression descriptor.  This file gives that packet format its exact
mathematical meaning.  It normalizes each span descriptor, proves that the
generated first-coordinate values implement the declared prefix drop, and
then identifies every normalized label group with the true arm of the actual
Cook--Levin dispatch mux.

Keeping this semantic bridge separate from the streaming controller makes the
machine proof small and gives it a precise, independently checked target.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- Normalize corresponding prefix-drop amounts and affine span descriptors.
Malformed unequal tables denote the empty family; the verifier-fixed tables
used below are proved to have equal lengths. -/
def transitionDispatchTrueArmSpanProgressionsFrom
    (seed : TransitionRowSeed) :
    List Nat → List TransitionWidenedFallbackSegment →
      List AffineUnaryTripleProgression
  | amount :: amounts, segment :: segments =>
      transitionStackRouteDropPrefix amount
          (transitionWidenedFallbackSegmentProgression seed segment) ::
        transitionDispatchTrueArmSpanProgressionsFrom seed amounts segments
  | _, _ => []

/-- One normalized span emits exactly the first-coordinate values remaining
after its declared prefix drop. -/
theorem transitionDispatchTrueArmSpanProgression_firstValues
    (seed : TransitionRowSeed) (amount : Nat)
    (segment : TransitionWidenedFallbackSegment) :
    transitionProgressionFirstValues
        (transitionStackRouteDropPrefix amount
          (transitionWidenedFallbackSegmentProgression seed segment)) =
      (transitionWidenedFallbackSegmentValues seed segment).drop amount := by
  unfold transitionProgressionFirstValues
    transitionWidenedFallbackSegmentValues
  rw [transitionStackRouteDropPrefix_rows, List.map_drop]

/-- Lock-step normalization has exactly the row semantics of the fixed-group
prefix-drop operation used by the existing true-arm compiler. -/
theorem transitionDispatchTrueArmSpanProgressionsFrom_firstValues
    (seed : TransitionRowSeed) :
    ∀ (amounts : List Nat)
      (segments : List TransitionWidenedFallbackSegment),
      amounts.length = segments.length →
      (transitionDispatchTrueArmSpanProgressionsFrom seed amounts segments).flatMap
          transitionProgressionFirstValues =
        unaryFrameFixedGroupPrefixDropValues amounts
          (transitionAffineSegmentValueRows seed segments) := by
  intro amounts
  induction amounts with
  | nil =>
      intro segments hlength
      have hnil : segments = [] := List.eq_nil_of_length_eq_zero hlength.symm
      subst segments
      rfl
  | cons amount amounts ih =>
      intro segments hlength
      cases segments with
      | nil => simp at hlength
      | cons segment segments =>
          simp only [List.length_cons] at hlength
          simp only [transitionDispatchTrueArmSpanProgressionsFrom,
            List.flatMap_cons, unaryFrameFixedGroupPrefixDropValues,
            transitionAffineSegmentValueRows, List.map_cons]
          rw [transitionDispatchTrueArmSpanProgression_firstValues]
          rw [ih segments (by omega)]
          rfl

/-- Normalized affine progressions of one label's complete true arm. -/
noncomputable def
    TransitionDispatchTrueArmNormalizedLayout.affineSpanProgressions
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (layout : TransitionDispatchTrueArmNormalizedLayout tm) :
    List AffineUnaryTripleProgression :=
  transitionDispatchTrueArmSpanProgressionsFrom seed
    (layout.affineSpanDropAmounts tm) (layout.affineSpanSegments tm)

/-- The normalized progressions of one label generate its complete established
descriptor route, with no lost or duplicated coordinates. -/
theorem
    TransitionDispatchTrueArmNormalizedLayout.affineSpanProgressions_values
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) (seed : TransitionRowSeed)
    (hseed : seed ∈ verifierTransitionRowSeeds W input)
    (layout : TransitionDispatchTrueArmNormalizedLayout W.machine.tm) :
    (layout.affineSpanProgressions W.machine.tm seed).flatMap
        transitionProgressionFirstValues =
      layout.descriptorValueRoute W.machine.tm seed := by
  unfold TransitionDispatchTrueArmNormalizedLayout.affineSpanProgressions
  rw [transitionDispatchTrueArmSpanProgressionsFrom_firstValues seed
    (layout.affineSpanDropAmounts W.machine.tm)
    (layout.affineSpanSegments W.machine.tm)
    (layout.affineSpanDropAmounts_length W.machine.tm)]
  exact layout.affineSpanSegments_values W input seed hseed

/-- One normalized progression group per program label, in dispatch order. -/
noncomputable def transitionDispatchTrueArmSpanProgressionGroups
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    List (List AffineUnaryTripleProgression) :=
  (transitionDispatchTrueArmNormalizedLayouts tm).map fun layout =>
    layout.affineSpanProgressions tm seed

/-- Executing the grouped normalized descriptors recovers every descriptor
true-arm row in the original program-label order. -/
theorem transitionDispatchTrueArmSpanProgressionGroups_values
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) (seed : TransitionRowSeed)
    (hseed : seed ∈ verifierTransitionRowSeeds W input) :
    (transitionDispatchTrueArmSpanProgressionGroups W.machine.tm seed).map
        (fun progressions =>
          progressions.flatMap transitionProgressionFirstValues) =
      transitionDispatchTrueArmDescriptorRoutes W.machine.tm seed := by
  unfold transitionDispatchTrueArmSpanProgressionGroups
    transitionDispatchTrueArmDescriptorRoutes
  rw [List.map_map]
  apply List.map_congr_left
  intro layout hlayout
  exact layout.affineSpanProgressions_values W input seed hseed

/-- For every verifier-produced transition seed, the normalized descriptor
groups are exactly the true-arm rows of the actual Cook--Levin dispatch muxes.
-/
theorem transitionDispatchTrueArmSpanProgressionGroups_eq_seed
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) (seed : TransitionRowSeed)
    (hseed : seed ∈ verifierTransitionRowSeeds W input) :
    (transitionDispatchTrueArmSpanProgressionGroups W.machine.tm seed).map
        (fun progressions =>
          progressions.flatMap transitionProgressionFirstValues) =
      transitionDispatchTrueArmRowsFromSeed W.machine.tm seed := by
  rw [transitionDispatchTrueArmSpanProgressionGroups_values W input seed hseed]
  apply transitionDispatchTrueArmDescriptorRoutes_eq_seed
  have hheight := verifierTransitionRowSeeds_height_eq W input seed hseed
  rw [hheight]
  unfold workHeight
  exact Nat.add_pos_left (verifierHeight_eval_pos W input.length) _

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