Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_bb82b2c75d23c9238afd0ebe

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_9b07aafd66df2f2eab4f6e2f
import Definitions.Def_PricingWithTips3DM_1c7b0450a7895da3606d9dbf
import Definitions.Def_PricingWithTips3DM_645fa74d60687a6229a5303d
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Physical encoding of typed label-major descriptor packets

The preceding modules expose the concrete source as a cyclic delimiter map
and the local interpretation contract as typed packets.  Here those two
interfaces are joined byte-for-byte.  Every complete delimiter cycle is one
transition seed; inside it, each verifier-fixed delimiter group is exactly
one marked typed label packet.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- Physical marked encoding of one typed descriptor packet. -/
def TransitionDispatchMuxInvocationLabelMajorDescriptorPacket.frames
    {tm : _root_.Turing.FinTM2} (seed : TransitionRowSeed)
    (packet : TransitionDispatchMuxInvocationLabelMajorDescriptorPacket tm) :
    List UnaryFrameSym :=
  encodeUnaryFrameFixedWidthPacket (packet.descriptorValues seed)

/-- Marker-free body used to package typed descriptors as a generic marked
row family. -/
def TransitionDispatchMuxInvocationLabelMajorDescriptorPacket.bodyFrames
    {tm : _root_.Turing.FinTM2} (seed : TransitionRowSeed)
    (packet : TransitionDispatchMuxInvocationLabelMajorDescriptorPacket tm) :
    List UnaryFrameSym :=
  encodeUnaryFrameFixedWidthPacketBody (packet.descriptorValues seed)

private theorem labelMajorFormGroups_fixed_encoding
    (seed : TransitionRowSeed) :
    ∀ (groups : List (List AffineUnaryTripleForm)),
      (∀ group ∈ groups, 0 < group.length) →
      encodeUnaryFrameWithFixedDelimiters
          ((groups.map fun group =>
            affineUnaryTripleMap group
              (transitionTailAffineSeed seed)).flatten)
          (groups.flatMap
            transitionDispatchMuxInvocationLabelMajorDescriptorGroupDelimiters) =
        (groups.map fun group =>
          affineUnaryTripleMap group
            (transitionTailAffineSeed seed)).flatMap
              encodeUnaryFrameFixedWidthPacket := by
  intro groups hnonempty
  induction groups with
  | nil => rfl
  | cons group groups ih =>
      let values := affineUnaryTripleMap group
        (transitionTailAffineSeed seed)
      have hgroup : 0 < group.length := hnonempty group (by simp)
      have hgroups : ∀ other ∈ groups, 0 < other.length := by
        intro other hother
        exact hnonempty other (by simp [hother])
      have hvaluesLength : values.length = group.length := by
        simp [values, affineUnaryTripleMap]
      have hvalues : values ≠ [] := by
        intro hempty
        rw [hempty] at hvaluesLength
        simp at hvaluesLength
        omega
      have hdelimiterLength :
          values.length =
            (transitionDispatchMuxInvocationLabelMajorDescriptorGroupDelimiters
              group).length := by
        simp [transitionDispatchMuxInvocationLabelMajorDescriptorGroupDelimiters,
          hvaluesLength]
        omega
      simp only [List.map_cons, List.flatten_cons, List.flatMap_cons]
      rw [encodeUnaryFrameWithFixedDelimiters_append _ _ _ _
        hdelimiterLength]
      rw [ih hgroups]
      apply congrArg (fun head =>
        head ++
          (groups.map fun other =>
            affineUnaryTripleMap other
              (transitionTailAffineSeed seed)).flatMap
                encodeUnaryFrameFixedWidthPacket)
      change encodeUnaryFrameWithFixedDelimiters values
          (transitionDispatchMuxInvocationLabelMajorDescriptorGroupDelimiters
            group) = encodeUnaryFrameFixedWidthPacket values
      unfold
        transitionDispatchMuxInvocationLabelMajorDescriptorGroupDelimiters
      rw [← hvaluesLength]
      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
    transitionDispatchMuxInvocationLabelMajorCanonicalDescriptorValueGroups_fixed_encoding
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    encodeUnaryFrameWithFixedDelimiters
        (transitionDispatchMuxInvocationLabelMajorCanonicalDescriptorValueGroups
          tm seed).flatten
        (transitionDispatchMuxInvocationLabelMajorDescriptorDelimiterTable tm) =
      (transitionDispatchMuxInvocationLabelMajorCanonicalDescriptorValueGroups
        tm seed).flatMap encodeUnaryFrameFixedWidthPacket := by
  rw [←
    transitionDispatchMuxInvocationLabelMajorDescriptorValueGroups_eq_canonical]
  unfold transitionDispatchMuxInvocationLabelMajorDescriptorValueGroups
    transitionDispatchMuxInvocationLabelMajorDescriptorDelimiterTable
  exact labelMajorFormGroups_fixed_encoding seed _
    (transitionDispatchMuxInvocationLabelMajorDescriptorFormGroups_nonempty tm)

private theorem
    transitionDispatchMuxInvocationLabelMajorCanonicalDescriptorValueGroups_flatten_length
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed) :
    (transitionDispatchMuxInvocationLabelMajorCanonicalDescriptorValueGroups
        tm seed).flatten.length =
      (transitionDispatchMuxInvocationLabelMajorDescriptorDelimiterTable
        tm).length := by
  rw [transitionDispatchMuxInvocationLabelMajorDescriptorDelimiterTable_length]
  rw [←
    transitionDispatchMuxInvocationLabelMajorDescriptorValueGroups_eq_canonical]
  unfold transitionDispatchMuxInvocationLabelMajorDescriptorValueGroups
    transitionDispatchMuxInvocationLabelMajorDescriptorForms
  simp only [List.length_flatten, List.map_map]
  apply congrArg List.sum
  apply List.map_congr_left
  intro group hgroup
  simp [affineUnaryTripleMap]

/-- The actual cyclic delimiter machine output is the seed-major,
label-major concatenation of typed packet encodings. -/
theorem
    verifierTransitionDispatchMuxInvocationLabelMajorMarkedDescriptorFrames_eq_packets
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierTransitionDispatchMuxInvocationLabelMajorMarkedDescriptorFrames
        W input =
      (verifierTransitionRowSeeds W input).flatMap fun seed =>
        (transitionDispatchMuxInvocationLabelMajorDescriptorPackets
          W.machine.tm seed).flatMap fun packet => packet.frames seed := by
  rw [
    verifierTransitionDispatchMuxInvocationLabelMajorMarkedDescriptorFrames_eq_canonical]
  unfold
    verifierTransitionDispatchMuxInvocationLabelMajorCanonicalMarkedDescriptorFrames
  rw [show
      (verifierTransitionRowSeeds W input).flatMap
          (fun seed =>
            (transitionDispatchMuxInvocationLabelMajorCanonicalDescriptorValueGroups
              W.machine.tm seed).flatten) =
        ((verifierTransitionRowSeeds W input).map fun seed =>
          (transitionDispatchMuxInvocationLabelMajorCanonicalDescriptorValueGroups
            W.machine.tm seed).flatten).flatten by
      induction verifierTransitionRowSeeds W input with
      | nil => rfl
      | cons seed seeds ih =>
          simp only [List.flatMap_cons, List.map_cons, List.flatten_cons]
          rw [ih]]
  rw [encodeUnaryFrameWithDelimiterCycle_eq_fixedRows]
  · rw [List.flatMap_map]
    apply List.flatMap_congr
    intro seed hseed
    rw [
      transitionDispatchMuxInvocationLabelMajorCanonicalDescriptorValueGroups_fixed_encoding]
    rw [←
      transitionDispatchMuxInvocationLabelMajorDescriptorPackets_values]
    simp [TransitionDispatchMuxInvocationLabelMajorDescriptorPacket.frames,
      List.flatMap_map]
  · intro row hrow
    rw [List.mem_map] at hrow
    rcases hrow with ⟨seed, hseed, rfl⟩
    exact
      transitionDispatchMuxInvocationLabelMajorCanonicalDescriptorValueGroups_flatten_length
        W.machine.tm seed

/-- Typed marked-row family physically emitted by the raw-input source. -/
noncomputable def
    verifierTransitionDispatchMuxInvocationLabelMajorDescriptorPacketFamily
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : UnaryFrameMarkedRowFamily :=
  { rows := (verifierTransitionRowSeeds W input).flatMap fun seed =>
      (transitionDispatchMuxInvocationLabelMajorDescriptorPackets
        W.machine.tm seed).map fun packet => packet.bodyFrames seed
    frameEnd_free := by
      intro row hrow symbol hsymbol
      rw [List.mem_flatMap] at hrow
      rcases hrow with ⟨seed, hseed, hrow⟩
      rw [List.mem_map] at hrow
      rcases hrow with ⟨packet, hpacket, rfl⟩
      exact encodeUnaryFrameFixedWidthPacketBody_frameEnd_free _ symbol
        hsymbol }

/-- The generic marked-row encoding of the typed family is byte-for-byte the
concrete label-major descriptor source. -/
theorem
    verifierTransitionDispatchMuxInvocationLabelMajorDescriptorPacketFamily_encoding_eq
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    encodeUnaryFrameMarkedRowFamily
        (verifierTransitionDispatchMuxInvocationLabelMajorDescriptorPacketFamily
          W input) =
      verifierTransitionDispatchMuxInvocationLabelMajorMarkedDescriptorFrames
        W input := by
  rw [
    verifierTransitionDispatchMuxInvocationLabelMajorMarkedDescriptorFrames_eq_packets]
  unfold encodeUnaryFrameMarkedRowFamily
    verifierTransitionDispatchMuxInvocationLabelMajorDescriptorPacketFamily
  rw [List.flatMap_assoc]
  apply List.flatMap_congr
  intro seed hseed
  rw [List.flatMap_map]
  apply List.flatMap_congr
  intro packet hpacket
  unfold
    TransitionDispatchMuxInvocationLabelMajorDescriptorPacket.bodyFrames
    TransitionDispatchMuxInvocationLabelMajorDescriptorPacket.frames
  have hne : packet.descriptorValues seed ≠ [] := by
    simp [TransitionDispatchMuxInvocationLabelMajorDescriptorPacket.descriptorValues]
  cases hvalues : packet.descriptorValues seed with
  | nil => exact False.elim (hne hvalues)
  | cons value values =>
      simpa [hvalues] using
        (encodeUnaryFrameFixedWidthPacket_eq_body value values).symm

/-- The raw verifier input is compiled by one concrete polynomial-time TM2
into the typed, physically marked descriptor packet family. -/
noncomputable def
    verifierTransitionDispatchMuxInvocationLabelMajorDescriptorPacketFamily_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id
      encodeUnaryFrameMarkedRowFamily
      (verifierTransitionDispatchMuxInvocationLabelMajorDescriptorPacketFamily
        W) := by
  let source :=
    verifierTransitionDispatchMuxInvocationLabelMajorMarkedDescriptorFrames_computableInPolyTime
      W
  exact
    { tm := source.tm
      inputAlphabet := source.inputAlphabet
      outputAlphabet := source.outputAlphabet
      time := source.time
      outputsFun := fun input => by
        have run := source.outputsFun input
        simpa only [id_eq,
          verifierTransitionDispatchMuxInvocationLabelMajorDescriptorPacketFamily_encoding_eq
            W input] using run }

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