Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_a5602838c2e55d3bf8d5e39a

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

/-!
# Exact packet semantics of the label-major four-row descriptor source

The concrete delimiter source now has a typed, byte-exact contract.  For
every transition seed and program label it emits, in order, one selector row,
one fresh-coordinate descriptor row, one normalized true-arm descriptor row,
and one false-arm descriptor row.  This is the physical input shape needed by
the remaining periodic descriptor interpreter.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- The four descriptor-value rows carried by one typed label packet. -/
def
    TransitionDispatchMuxInvocationLabelMajorDescriptorPacket.fourRowDescriptorValueGroups
    {tm : _root_.Turing.FinTM2} (seed : TransitionRowSeed)
    (packet : TransitionDispatchMuxInvocationLabelMajorDescriptorPacket tm) :
    List (List Nat) :=
  [ [packet.selector],
    transitionDispatchProgressionDescriptorValues
      packet.coordinateProgressions,
    packet.trueLayout.affineSpanDescriptorValues tm seed,
    transitionDispatchProgressionDescriptorValues packet.falseProgressions ]

/-- Physical marked encoding of the four descriptor rows of one label. -/
def
    TransitionDispatchMuxInvocationLabelMajorDescriptorPacket.fourRowDescriptorFrames
    {tm : _root_.Turing.FinTM2} (seed : TransitionRowSeed)
    (packet : TransitionDispatchMuxInvocationLabelMajorDescriptorPacket tm) :
    List UnaryFrameSym :=
  (packet.fourRowDescriptorValueGroups seed).flatMap
    encodeUnaryFrameFixedWidthPacket

private theorem
    transitionDispatchMuxInvocationLabelMajorDescriptorPacketsFrom_fourRows
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (selectors : List Nat)
    (coordinateGroups : List (List AffineUnaryTripleProgression))
    (trueLayouts : List (TransitionDispatchTrueArmNormalizedLayout tm))
    (falseGroups : List (List AffineUnaryTripleProgression)) :
    (transitionDispatchMuxInvocationLabelMajorDescriptorPacketsFrom tm
        selectors coordinateGroups trueLayouts falseGroups).flatMap
        (fun packet => packet.fourRowDescriptorValueGroups seed) =
      transitionDispatchMuxInvocationLabelMajorFourRowDescriptorValueGroupsFrom
        selectors
        (coordinateGroups.map transitionDispatchProgressionDescriptorValues)
        (trueLayouts.map fun layout =>
          layout.affineSpanDescriptorValues tm seed)
        (falseGroups.map transitionDispatchProgressionDescriptorValues) := by
  induction selectors generalizing coordinateGroups trueLayouts falseGroups with
  | nil => rfl
  | cons selector selectors ih =>
      cases coordinateGroups with
      | nil => rfl
      | cons coordinates coordinateGroups =>
          cases trueLayouts with
          | nil => rfl
          | cons trueLayout trueLayouts =>
              cases falseGroups with
              | nil => rfl
              | cons whenFalse falseGroups =>
                  change
                    [[selector],
                      transitionDispatchProgressionDescriptorValues coordinates,
                      trueLayout.affineSpanDescriptorValues tm seed,
                      transitionDispatchProgressionDescriptorValues whenFalse] ++
                        (transitionDispatchMuxInvocationLabelMajorDescriptorPacketsFrom
                          tm selectors coordinateGroups trueLayouts
                          falseGroups).flatMap
                            (fun packet =>
                              packet.fourRowDescriptorValueGroups seed) =
                      [[selector],
                        transitionDispatchProgressionDescriptorValues coordinates,
                        trueLayout.affineSpanDescriptorValues tm seed,
                        transitionDispatchProgressionDescriptorValues whenFalse] ++
                          transitionDispatchMuxInvocationLabelMajorFourRowDescriptorValueGroupsFrom
                            selectors
                            (coordinateGroups.map
                              transitionDispatchProgressionDescriptorValues)
                            (trueLayouts.map fun layout =>
                              layout.affineSpanDescriptorValues tm seed)
                            (falseGroups.map
                              transitionDispatchProgressionDescriptorValues)
                  rw [ih coordinateGroups trueLayouts falseGroups]

/-- Flattening the four rows of every typed packet gives the canonical
seed-local four-row value family. -/
theorem
    transitionDispatchMuxInvocationLabelMajorDescriptorPackets_fourRows
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    (transitionDispatchMuxInvocationLabelMajorDescriptorPackets tm seed).flatMap
        (fun packet => packet.fourRowDescriptorValueGroups seed) =
      transitionDispatchMuxInvocationLabelMajorCanonicalFourRowDescriptorValueGroups
        tm seed := by
  unfold transitionDispatchMuxInvocationLabelMajorDescriptorPackets
    transitionDispatchMuxInvocationLabelMajorCanonicalFourRowDescriptorValueGroups
  exact
    transitionDispatchMuxInvocationLabelMajorDescriptorPacketsFrom_fourRows
      tm seed _ _ _ _

private theorem
    transitionDispatchMuxInvocationLabelMajorSectionDelimiters_encoding
    (seed : TransitionRowSeed) (forms : List AffineUnaryTripleForm) :
    encodeUnaryFrameWithFixedDelimiters
        (affineUnaryTripleMap forms (transitionTailAffineSeed seed))
        (transitionDispatchMuxInvocationLabelMajorSectionDelimiters forms) =
      encodeUnaryFrameFixedWidthPacket
        (affineUnaryTripleMap forms (transitionTailAffineSeed seed)) := by
  cases forms with
  | nil =>
      simp [affineUnaryTripleMap,
        transitionDispatchMuxInvocationLabelMajorSectionDelimiters,
        encodeUnaryFrameWithFixedDelimiters,
        encodeUnaryFrameFixedWidthPacket]
  | cons form forms =>
      let values := affineUnaryTripleMap (form :: forms)
        (transitionTailAffineSeed seed)
      have hvalues : values ≠ [] := by
        simp [values, affineUnaryTripleMap]
      have hdelimiters :
          transitionDispatchMuxInvocationLabelMajorSectionDelimiters
              (form :: forms) =
            List.replicate forms.length .separator ++ [.frameEnd] := by
        apply List.ext_getElem
        · simp [transitionDispatchMuxInvocationLabelMajorSectionDelimiters]
        · intro index hleft hright
          simp only [
            transitionDispatchMuxInvocationLabelMajorSectionDelimiters,
            List.getElem_ofFn]
          have hbound : index < forms.length + 1 := by
            simpa [
              transitionDispatchMuxInvocationLabelMajorSectionDelimiters]
              using hleft
          by_cases hindex : index < forms.length
          · have hnotIndex : ¬index = forms.length := by omega
            simp [hindex, hnotIndex]
          · have hlast : index = forms.length := by omega
            subst index
            simp
      change encodeUnaryFrameWithFixedDelimiters values _ =
        encodeUnaryFrameFixedWidthPacket values
      rw [hdelimiters]
      have hlength : values.length - 1 = forms.length := by
        simp [values, affineUnaryTripleMap]
      rw [← hlength]
      rw [encodeUnaryFrameWithOwnFinalDelimiter values .frameEnd hvalues]
      cases hvaluesEq : values with
      | nil => exact False.elim (hvalues hvaluesEq)
      | cons value rest =>
          simpa [hvaluesEq] using
            (encodeUnaryFrameFixedWidthPacket_eq_body value rest).symm

private theorem
    transitionDispatchMuxInvocationLabelMajorFourRowForms_fixed_encoding
    (seed : TransitionRowSeed) :
    ∀ (selectors : List AffineUnaryTripleForm)
      (coordinateGroups trueGroups falseGroups :
        List (List AffineUnaryTripleForm)),
      encodeUnaryFrameWithFixedDelimiters
          ((transitionDispatchMuxInvocationLabelMajorDescriptorFormGroupsFrom
            selectors coordinateGroups trueGroups falseGroups).map
              (fun group => affineUnaryTripleMap group
                (transitionTailAffineSeed seed))).flatten
          (transitionDispatchMuxInvocationLabelMajorFourRowDescriptorDelimiterGroupsFrom
            selectors coordinateGroups trueGroups falseGroups).flatten =
        (transitionDispatchMuxInvocationLabelMajorFourRowDescriptorValueGroupsFrom
          (affineUnaryTripleMap selectors (transitionTailAffineSeed seed))
          (coordinateGroups.map fun group => affineUnaryTripleMap group
            (transitionTailAffineSeed seed))
          (trueGroups.map fun group => affineUnaryTripleMap group
            (transitionTailAffineSeed seed))
          (falseGroups.map fun group => affineUnaryTripleMap group
            (transitionTailAffineSeed seed))).flatMap
              encodeUnaryFrameFixedWidthPacket := by
  intro selectors coordinateGroups trueGroups falseGroups
  induction selectors generalizing coordinateGroups trueGroups falseGroups with
  | nil => rfl
  | cons selector selectors ih =>
      cases coordinateGroups with
      | nil => rfl
      | cons coordinates coordinateGroups =>
          cases trueGroups with
          | nil => rfl
          | cons whenTrue trueGroups =>
              cases falseGroups with
              | nil => rfl
              | cons whenFalse falseGroups =>
                  have hhead :
                      (affineUnaryTripleMap
                        (selector :: coordinates ++ whenTrue ++ whenFalse)
                        (transitionTailAffineSeed seed)).length =
                        ([UnaryFrameSym.frameEnd] ++
                          transitionDispatchMuxInvocationLabelMajorSectionDelimiters
                            coordinates ++
                          transitionDispatchMuxInvocationLabelMajorSectionDelimiters
                            whenTrue ++
                          transitionDispatchMuxInvocationLabelMajorSectionDelimiters
                            whenFalse).length := by
                    simp [affineUnaryTripleMap,
                      transitionDispatchMuxInvocationLabelMajorSectionDelimiters]
                  simp only [
                    transitionDispatchMuxInvocationLabelMajorDescriptorFormGroupsFrom,
                    transitionDispatchMuxInvocationLabelMajorFourRowDescriptorDelimiterGroupsFrom,
                    List.map_cons, List.flatten_cons]
                  rw [encodeUnaryFrameWithFixedDelimiters_append _ _ _ _ hhead]
                  rw [ih coordinateGroups trueGroups falseGroups]
                  simp only [affineUnaryTripleMap, List.map_cons,
                    transitionDispatchMuxInvocationLabelMajorFourRowDescriptorValueGroupsFrom,
                    List.flatMap_append, List.flatMap_cons,
                    List.flatMap_nil, List.append_nil]
                  apply congrArg (fun head => head ++ _)
                  simp only [List.map_cons, List.map_append]
                  change encodeUnaryFrameWithFixedDelimiters
                      ([affineUnaryTripleFormValue selector
                          (transitionTailAffineSeed seed)] ++
                        (affineUnaryTripleMap coordinates
                            (transitionTailAffineSeed seed) ++
                          affineUnaryTripleMap whenTrue
                            (transitionTailAffineSeed seed) ++
                          affineUnaryTripleMap whenFalse
                            (transitionTailAffineSeed seed)))
                      ([UnaryFrameSym.frameEnd] ++
                        (transitionDispatchMuxInvocationLabelMajorSectionDelimiters
                            coordinates ++
                          transitionDispatchMuxInvocationLabelMajorSectionDelimiters
                            whenTrue ++
                          transitionDispatchMuxInvocationLabelMajorSectionDelimiters
                            whenFalse)) =
                    encodeUnaryFrameFixedWidthPacket
                        [affineUnaryTripleFormValue selector
                          (transitionTailAffineSeed seed)] ++
                      (encodeUnaryFrameFixedWidthPacket
                          (affineUnaryTripleMap coordinates
                            (transitionTailAffineSeed seed)) ++
                        (encodeUnaryFrameFixedWidthPacket
                            (affineUnaryTripleMap whenTrue
                              (transitionTailAffineSeed seed)) ++
                          encodeUnaryFrameFixedWidthPacket
                            (affineUnaryTripleMap whenFalse
                              (transitionTailAffineSeed seed))))
                  rw [encodeUnaryFrameWithFixedDelimiters_append
                    [_]
                    (affineUnaryTripleMap coordinates
                        (transitionTailAffineSeed seed) ++
                      affineUnaryTripleMap whenTrue
                        (transitionTailAffineSeed seed) ++
                      affineUnaryTripleMap whenFalse
                        (transitionTailAffineSeed seed))
                    [UnaryFrameSym.frameEnd]
                    (transitionDispatchMuxInvocationLabelMajorSectionDelimiters
                        coordinates ++
                      transitionDispatchMuxInvocationLabelMajorSectionDelimiters
                        whenTrue ++
                      transitionDispatchMuxInvocationLabelMajorSectionDelimiters
                        whenFalse)
                    (by simp)]
                  rw [List.append_assoc
                    (affineUnaryTripleMap coordinates
                      (transitionTailAffineSeed seed))
                    (affineUnaryTripleMap whenTrue
                      (transitionTailAffineSeed seed))
                    (affineUnaryTripleMap whenFalse
                      (transitionTailAffineSeed seed))]
                  rw [List.append_assoc
                    (transitionDispatchMuxInvocationLabelMajorSectionDelimiters
                      coordinates)
                    (transitionDispatchMuxInvocationLabelMajorSectionDelimiters
                      whenTrue)
                    (transitionDispatchMuxInvocationLabelMajorSectionDelimiters
                      whenFalse)]
                  rw [encodeUnaryFrameWithFixedDelimiters_append
                    (affineUnaryTripleMap coordinates
                      (transitionTailAffineSeed seed))
                    (affineUnaryTripleMap whenTrue
                        (transitionTailAffineSeed seed) ++
                      affineUnaryTripleMap whenFalse
                        (transitionTailAffineSeed seed))
                    (transitionDispatchMuxInvocationLabelMajorSectionDelimiters
                      coordinates)
                    (transitionDispatchMuxInvocationLabelMajorSectionDelimiters
                        whenTrue ++
                      transitionDispatchMuxInvocationLabelMajorSectionDelimiters
                        whenFalse)
                    (by simp [affineUnaryTripleMap])]
                  rw [encodeUnaryFrameWithFixedDelimiters_append
                    (affineUnaryTripleMap whenTrue
                      (transitionTailAffineSeed seed))
                    (affineUnaryTripleMap whenFalse
                      (transitionTailAffineSeed seed))
                    (transitionDispatchMuxInvocationLabelMajorSectionDelimiters
                      whenTrue)
                    (transitionDispatchMuxInvocationLabelMajorSectionDelimiters
                      whenFalse)
                    (by simp [affineUnaryTripleMap])]
                  simp only [encodeUnaryFrameWithFixedDelimiters,
                    encodeUnaryFrameFixedWidthPacket]
                  rw [
                    transitionDispatchMuxInvocationLabelMajorSectionDelimiters_encoding
                      seed coordinates]
                  rw [
                    transitionDispatchMuxInvocationLabelMajorSectionDelimiters_encoding
                      seed whenTrue]
                  rw [
                    transitionDispatchMuxInvocationLabelMajorSectionDelimiters_encoding
                      seed whenFalse]

/-- The actual raw-input source is exactly the seed-major, label-major
concatenation of four physical descriptor rows from every typed packet. -/
theorem
    verifierTransitionDispatchMuxInvocationLabelMajorFourRowDescriptorFrames_eq_packets
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierTransitionDispatchMuxInvocationLabelMajorFourRowDescriptorFrames
        W input =
      (verifierTransitionRowSeeds W input).flatMap fun seed =>
        (transitionDispatchMuxInvocationLabelMajorDescriptorPackets
          W.machine.tm seed).flatMap fun packet =>
            packet.fourRowDescriptorFrames seed := by
  rw [
    verifierTransitionDispatchMuxInvocationLabelMajorFourRowDescriptorFrames_eq]
  apply List.flatMap_congr
  intro seed hseed
  rw [←
    transitionDispatchMuxInvocationLabelMajorDescriptorValueGroups_eq_canonical]
  unfold transitionDispatchMuxInvocationLabelMajorDescriptorValueGroups
    transitionDispatchMuxInvocationLabelMajorDescriptorFormGroups
    transitionDispatchMuxInvocationLabelMajorFourRowDescriptorDelimiterTable
    transitionDispatchMuxInvocationLabelMajorFourRowDescriptorDelimiterGroups
  rw [
    transitionDispatchMuxInvocationLabelMajorFourRowForms_fixed_encoding seed]
  rw [←
    transitionDispatchMuxInvocationLabelMajorCanonicalFourRowDescriptorValueGroups_eq_forms]
  rw [←
    transitionDispatchMuxInvocationLabelMajorDescriptorPackets_fourRows]
  simp [
    TransitionDispatchMuxInvocationLabelMajorDescriptorPacket.fourRowDescriptorFrames,
    List.flatMap_assoc]

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