Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_d31d920ac0b45f37a1290211

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

/-!
# True-arm descriptors from label-major dispatch packets

The third row of every physical label-major packet contains the complete
normalized true-arm descriptor payload for that label.  This module selects
those rows, removes their temporary label markers, and proves that the result
is exactly the established adjacent eight-field true-arm block stream.  All
later verified true-arm interpreters can therefore be reused unchanged.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

private theorem
    transitionDispatchMuxInvocationLabelMajorDescriptorPacketsFrom_trueLayouts
    (tm : _root_.Turing.FinTM2)
    (selectors : List Nat)
    (coordinateGroups : List (List AffineUnaryTripleProgression))
    (trueLayouts : List (TransitionDispatchTrueArmNormalizedLayout tm))
    (falseGroups : List (List AffineUnaryTripleProgression))
    (hcoordinate : coordinateGroups.length = selectors.length)
    (htrue : trueLayouts.length = selectors.length)
    (hfalse : falseGroups.length = selectors.length) :
    (transitionDispatchMuxInvocationLabelMajorDescriptorPacketsFrom tm
        selectors coordinateGroups trueLayouts falseGroups).map
        (fun packet => packet.trueLayout) = trueLayouts := by
  induction selectors generalizing coordinateGroups trueLayouts falseGroups with
  | nil =>
      simp only [List.length_nil] at htrue
      have htrueNil : trueLayouts = [] := by simpa using htrue
      subst trueLayouts
      rfl
  | cons selector selectors ih =>
      cases coordinateGroups with
      | nil => simp at hcoordinate
      | cons coordinates coordinateGroups =>
          cases trueLayouts with
          | nil => simp at htrue
          | cons trueLayout trueLayouts =>
              cases falseGroups with
              | nil => simp at hfalse
              | cons whenFalse falseGroups =>
                  simp only [
                    transitionDispatchMuxInvocationLabelMajorDescriptorPacketsFrom,
                    List.map_cons]
                  congr 1
                  apply ih
                  · simpa using hcoordinate
                  · simpa using htrue
                  · simpa using hfalse

/-- Projecting the third field of every typed packet recovers the verifier-
fixed normalized true layouts. -/
theorem transitionDispatchMuxInvocationLabelMajorDescriptorPackets_trueLayouts
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) (seed : TransitionRowSeed)
    (hseed : seed ∈ verifierTransitionRowSeeds W input) :
    (transitionDispatchMuxInvocationLabelMajorDescriptorPackets
        W.machine.tm seed).map (fun packet => packet.trueLayout) =
      transitionDispatchTrueArmNormalizedLayouts W.machine.tm := by
  unfold transitionDispatchMuxInvocationLabelMajorDescriptorPackets
  apply
    transitionDispatchMuxInvocationLabelMajorDescriptorPacketsFrom_trueLayouts
  · rw [transitionDispatchMuxCoordinateProgressionGroups_length,
      transitionDispatchSelectors_length]
  · have hlength :=
      transitionDispatchTrueArmSpanProgressionGroups_length W.machine.tm seed
    unfold transitionDispatchTrueArmSpanProgressionGroups at hlength
    simp only [List.length_map] at hlength
    rw [hlength, transitionDispatchSelectors_length]
  · rw [transitionDispatchFalseArmProgressionGroups_length W input seed hseed,
      transitionDispatchSelectors_length]

/-- Select the third row of each selector/coordinate/true/false packet. -/
def transitionDispatchMuxInvocationLabelMajorTrueSelection : List Bool :=
  [false, false, true, false]

theorem transitionDispatchMuxInvocationLabelMajorTrueSelection_nonempty :
    0 < transitionDispatchMuxInvocationLabelMajorTrueSelection.length := by
  simp [transitionDispatchMuxInvocationLabelMajorTrueSelection]

/-- Selected, still label-marked true-arm descriptor rows. -/
noncomputable def verifierTransitionDispatchMuxInvocationLabelMajorTrueMarkedRows
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List UnaryFrameSym :=
  rewriteUnaryFramePeriodicMarkedRows
    transitionDispatchMuxInvocationLabelMajorTrueSelection
    transitionDispatchMuxInvocationLabelMajorTrueSelection_nonempty
    (verifierTransitionDispatchMuxInvocationLabelMajorFourRowNormalizedFrames
      W input)

/-- The selected physical rows carry precisely each packet's normalized
true-arm span descriptors. -/
theorem verifierTransitionDispatchMuxInvocationLabelMajorTrueMarkedRows_eq
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierTransitionDispatchMuxInvocationLabelMajorTrueMarkedRows W input =
      (verifierTransitionRowSeeds W input).flatMap fun seed =>
        (transitionDispatchMuxInvocationLabelMajorDescriptorPackets
          W.machine.tm seed).flatMap fun packet =>
            encodeUnaryFrame
                (packet.trueLayout.affineSpanDescriptorValues
                  W.machine.tm seed) ++ [.frameEnd] := by
  unfold verifierTransitionDispatchMuxInvocationLabelMajorTrueMarkedRows
  rw [
    verifierTransitionDispatchMuxInvocationLabelMajorFourRowNormalizedFrames_eq]
  rw [rewriteUnaryFramePeriodicMarkedRows_encode]
  rw [encodeUnaryFramePeriodicMarkedRowOutput_groups _ _ _]
  · unfold
      verifierTransitionDispatchMuxInvocationLabelMajorFourRowDescriptorValueGroups
    rw [List.flatMap_assoc]
    apply List.flatMap_congr
    intro seed hseed
    rw [List.flatMap_map]
    apply List.flatMap_congr
    intro packet hpacket
    simp [transitionDispatchMuxInvocationLabelMajorTrueSelection,
      TransitionDispatchMuxInvocationLabelMajorDescriptorPacket.fourRowDescriptorValueGroups,
      encodeUnaryFramePeriodicSelectedMarkedRows]
  · intro group hgroup
    simpa [transitionDispatchMuxInvocationLabelMajorTrueSelection] using
      (verifierTransitionDispatchMuxInvocationLabelMajorFourRowDescriptorValueGroups_length
        W input group hgroup)

/-- Remove temporary label markers and expose the adjacent true-arm block
stream expected by the established eight-to-seven-field interpreter. -/
noncomputable def verifierTransitionDispatchMuxInvocationLabelMajorTrueFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List UnaryFrameSym :=
  unmarkAffineUnaryTripleProgressionRows
    (verifierTransitionDispatchMuxInvocationLabelMajorTrueMarkedRows W input)

theorem verifierTransitionDispatchMuxInvocationLabelMajorTrueFrames_eq_values
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierTransitionDispatchMuxInvocationLabelMajorTrueFrames W input =
      encodeUnaryFrame
        ((verifierTransitionRowSeeds W input).flatMap fun seed =>
          (transitionDispatchMuxInvocationLabelMajorDescriptorPackets
            W.machine.tm seed).flatMap fun packet =>
              packet.trueLayout.affineSpanDescriptorValues
                W.machine.tm seed) := by
  unfold verifierTransitionDispatchMuxInvocationLabelMajorTrueFrames
  rw [verifierTransitionDispatchMuxInvocationLabelMajorTrueMarkedRows_eq]
  rw [show
      (verifierTransitionRowSeeds W input).flatMap
          (fun seed =>
            (transitionDispatchMuxInvocationLabelMajorDescriptorPackets
              W.machine.tm seed).flatMap fun packet =>
                encodeUnaryFrame
                    (packet.trueLayout.affineSpanDescriptorValues
                      W.machine.tm seed) ++ [.frameEnd]) =
        (((verifierTransitionRowSeeds W input).flatMap fun seed =>
          (transitionDispatchMuxInvocationLabelMajorDescriptorPackets
            W.machine.tm seed).map fun packet =>
              packet.trueLayout.affineSpanDescriptorValues
                W.machine.tm seed).flatMap fun row =>
                  encodeUnaryFrame row ++ [.frameEnd]) by
      simp [List.flatMap_assoc, List.flatMap_map]]
  rw [unmarkAffineUnaryTripleProgressionRows_markedValues]
  congr 1
  rw [List.flatten_eq_flatMap, List.flatMap_assoc]
  apply List.flatMap_congr
  intro seed hseed
  rw [List.flatMap_map]
  simp only [id_eq]

/-- The label-major true descriptor bytes are byte-for-byte the established
true descriptor channel. -/
theorem verifierTransitionDispatchMuxInvocationLabelMajorTrueFrames_eq_existing
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierTransitionDispatchMuxInvocationLabelMajorTrueFrames W input =
      verifierTransitionDispatchMuxInvocationDescriptorTrueFrames W input := by
  rw [verifierTransitionDispatchMuxInvocationLabelMajorTrueFrames_eq_values,
    verifierTransitionDispatchMuxInvocationDescriptorTrueFrames_eq_values]
  congr 1
  apply List.flatMap_congr
  intro seed hseed
  have hlayouts :=
    transitionDispatchMuxInvocationLabelMajorDescriptorPackets_trueLayouts
      W input seed hseed
  have hvalues := congrArg
    (List.flatMap fun layout =>
      layout.affineSpanDescriptorValues W.machine.tm seed) hlayouts
  simpa [List.flatMap_map, Function.comp_def,
    transitionDispatchTrueArmSpanDescriptorValues] using hvalues

noncomputable def
    verifierTransitionDispatchMuxInvocationLabelMajorTrueMarkedRows_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierTransitionDispatchMuxInvocationLabelMajorTrueMarkedRows W) := by
  let composed :=
    _root_.Turing.TM2Comp.TM2ComputableInPolyTime.comp_scratch
      (verifierTransitionDispatchMuxInvocationLabelMajorFourRowNormalizedFrames_computableInPolyTime
        W)
      (unaryFramePeriodicMarkedRowFilter_computableInPolyTime
        transitionDispatchMuxInvocationLabelMajorTrueSelection
        transitionDispatchMuxInvocationLabelMajorTrueSelection_nonempty)
  change _root_.Turing.TM2ComputableInPolyTime id id
    (fun input => rewriteUnaryFramePeriodicMarkedRows
      transitionDispatchMuxInvocationLabelMajorTrueSelection
      transitionDispatchMuxInvocationLabelMajorTrueSelection_nonempty
      (verifierTransitionDispatchMuxInvocationLabelMajorFourRowNormalizedFrames
        W input))
  simpa [Function.comp_def] using Classical.choice composed

/-- The raw verifier input reaches the exact established true descriptor
block stream through the label-major source in polynomial time. -/
noncomputable def
    verifierTransitionDispatchMuxInvocationLabelMajorTrueFrames_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierTransitionDispatchMuxInvocationLabelMajorTrueFrames W) := by
  let composed :=
    _root_.Turing.TM2Comp.TM2ComputableInPolyTime.comp_scratch
      (verifierTransitionDispatchMuxInvocationLabelMajorTrueMarkedRows_computableInPolyTime
        W)
      unmarkAffineUnaryTripleProgressionRows_computableInPolyTime
  change _root_.Turing.TM2ComputableInPolyTime id id
    (fun input => unmarkAffineUnaryTripleProgressionRows
      (verifierTransitionDispatchMuxInvocationLabelMajorTrueMarkedRows
        W input))
  simpa [Function.comp_def] using Classical.choice composed

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