Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_70e949f1de7d8f9866352485

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_8c1e30c9d40f5a908d6541b8
import Definitions.Def_PricingWithTips3DM_b39eb8a26337ad48e5bfb5ca
import Definitions.Def_PricingWithTips3DM_737c20b8086e2cd9790fc0ce
import Definitions.Def_PricingWithTips3DM_d5e5509d5077fe4dd724c010
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Concrete label-packet compiler from the four label-major channels

The four independently verified channels are first exposed as typed marked-row
families.  Three applications of the reusable same-input interleaver implement
the physical four-way zipper:

`(selector ⊗ true) ⊗ (coordinate ⊗ false)`

which emits `selector / coordinate / true / false` for every label.  The final
encoding is proved byte-for-byte equal to the typed label-packet input expected
by the existing assembler pipeline.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

private theorem labelChannel_encodeUnaryFrame_frameEnd_free
    (values : List Nat) :
    ∀ symbol ∈ encodeUnaryFrame values,
      symbol ≠ UnaryFrameSym.frameEnd := by
  intro symbol hsymbol
  rw [encodeUnaryFrame, List.mem_flatMap] at hsymbol
  rcases hsymbol with ⟨value, _, hblock⟩
  simp [encodeUnaryFrameBlock] at hblock
  rcases hblock with ⟨_, rfl⟩ | rfl <;> simp

private theorem labelChannel_coordinate_frameEnd_free
    (coordinates : List (Nat × Nat × Nat)) :
    ∀ symbol ∈ transitionDispatchMuxCoordinateRowFrames coordinates,
      symbol ≠ UnaryFrameSym.frameEnd := by
  intro symbol hsymbol
  rw [transitionDispatchMuxCoordinateRowFrames,
    List.mem_flatMap] at hsymbol
  rcases hsymbol with ⟨coordinate, _, hcoordinate⟩
  exact labelChannel_encodeUnaryFrame_frameEnd_free _ symbol hcoordinate

/-- Typed selector channel. -/
noncomputable def
    verifierTransitionDispatchMuxInvocationLabelMajorSelectorFamily
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : UnaryFrameMarkedRowFamily where
  rows :=
    (verifierTransitionDispatchMuxInvocationDescriptorLabelPacketChannelFamily
      W input).selectorRows
  frameEnd_free := by
    intro row hrow symbol hsymbol
    unfold
      verifierTransitionDispatchMuxInvocationDescriptorLabelPacketChannelFamily
      at hrow
    rw [List.mem_map] at hrow
    rcases hrow with ⟨view, _, rfl⟩
    exact labelChannel_encodeUnaryFrame_frameEnd_free _ symbol hsymbol

/-- Typed coordinate channel. -/
noncomputable def
    verifierTransitionDispatchMuxInvocationLabelMajorCoordinateFamily
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : UnaryFrameMarkedRowFamily where
  rows :=
    (verifierTransitionDispatchMuxInvocationDescriptorLabelPacketChannelFamily
      W input).coordinateRows
  frameEnd_free := by
    intro row hrow symbol hsymbol
    unfold
      verifierTransitionDispatchMuxInvocationDescriptorLabelPacketChannelFamily
      at hrow
    rw [List.mem_map] at hrow
    rcases hrow with ⟨view, _, rfl⟩
    exact labelChannel_coordinate_frameEnd_free _ symbol hsymbol

/-- Typed true-arm channel. -/
noncomputable def
    verifierTransitionDispatchMuxInvocationLabelMajorTrueFamily
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : UnaryFrameMarkedRowFamily where
  rows :=
    (verifierTransitionDispatchMuxInvocationDescriptorLabelPacketChannelFamily
      W input).trueRows
  frameEnd_free := by
    intro row hrow symbol hsymbol
    unfold
      verifierTransitionDispatchMuxInvocationDescriptorLabelPacketChannelFamily
      at hrow
    rw [List.mem_map] at hrow
    rcases hrow with ⟨view, _, rfl⟩
    exact labelChannel_encodeUnaryFrame_frameEnd_free _ symbol hsymbol

/-- Typed false-arm channel. -/
noncomputable def
    verifierTransitionDispatchMuxInvocationLabelMajorFalseFamily
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : UnaryFrameMarkedRowFamily where
  rows :=
    (verifierTransitionDispatchMuxInvocationDescriptorLabelPacketChannelFamily
      W input).falseRows
  frameEnd_free := by
    intro row hrow symbol hsymbol
    unfold
      verifierTransitionDispatchMuxInvocationDescriptorLabelPacketChannelFamily
      at hrow
    rw [List.mem_map] at hrow
    rcases hrow with ⟨view, _, rfl⟩
    exact labelChannel_encodeUnaryFrame_frameEnd_free _ symbol hsymbol

theorem
    verifierTransitionDispatchMuxInvocationLabelMajorChannelFamily_encodings
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    encodeUnaryFrameMarkedRowFamily
          (verifierTransitionDispatchMuxInvocationLabelMajorSelectorFamily
            W input) =
        verifierTransitionDispatchMuxInvocationLabelMajorSelectorLabelFrames
          W input ∧
      encodeUnaryFrameMarkedRowFamily
          (verifierTransitionDispatchMuxInvocationLabelMajorCoordinateFamily
            W input) =
        verifierTransitionDispatchMuxInvocationLabelMajorCoordinateLabelFrames
          W input ∧
      encodeUnaryFrameMarkedRowFamily
          (verifierTransitionDispatchMuxInvocationLabelMajorTrueFamily
            W input) =
        verifierTransitionDispatchMuxInvocationLabelMajorTrueLabelFrames
          W input ∧
      encodeUnaryFrameMarkedRowFamily
          (verifierTransitionDispatchMuxInvocationLabelMajorFalseFamily
            W input) =
        verifierTransitionDispatchMuxInvocationLabelMajorFalseLabelFrames
          W input := by
  have hchannels :=
    verifierTransitionDispatchMuxInvocationDescriptorLabelPacketChannelFamily_encodings
      W input
  rcases hchannels with ⟨hselector, hcoordinate, htrue, hfalse⟩
  constructor
  · exact hselector.trans
      (verifierTransitionDispatchMuxInvocationLabelMajorSelectorLabelFrames_eq_channel
        W input).symm
  constructor
  · exact hcoordinate.trans
      (verifierTransitionDispatchMuxInvocationLabelMajorCoordinateLabelFrames_eq_channel
        W input).symm
  constructor
  · exact htrue.trans
      (verifierTransitionDispatchMuxInvocationLabelMajorTrueLabelFrames_eq_channel
        W input).symm
  · exact hfalse.trans
      (verifierTransitionDispatchMuxInvocationLabelMajorFalseLabelFrames_eq_channel
        W input).symm

private noncomputable def selectorFamilyCompiler
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id
      encodeUnaryFrameMarkedRowFamily
      (verifierTransitionDispatchMuxInvocationLabelMajorSelectorFamily W) := by
  let base :=
    verifierTransitionDispatchMuxInvocationLabelMajorSelectorLabelFrames_computableInPolyTime
      W
  exact
    { tm := base.tm
      inputAlphabet := base.inputAlphabet
      outputAlphabet := base.outputAlphabet
      time := base.time
      outputsFun := fun input => by
        have run := base.outputsFun input
        simpa only [id_eq,
          (verifierTransitionDispatchMuxInvocationLabelMajorChannelFamily_encodings
            W input).1] using run }

private noncomputable def coordinateFamilyCompiler
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id
      encodeUnaryFrameMarkedRowFamily
      (verifierTransitionDispatchMuxInvocationLabelMajorCoordinateFamily W) := by
  let base :=
    verifierTransitionDispatchMuxInvocationLabelMajorCoordinateLabelFrames_computableInPolyTime
      W
  exact
    { tm := base.tm
      inputAlphabet := base.inputAlphabet
      outputAlphabet := base.outputAlphabet
      time := base.time
      outputsFun := fun input => by
        have run := base.outputsFun input
        simpa only [id_eq,
          (verifierTransitionDispatchMuxInvocationLabelMajorChannelFamily_encodings
            W input).2.1] using run }

private noncomputable def trueFamilyCompiler
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id
      encodeUnaryFrameMarkedRowFamily
      (verifierTransitionDispatchMuxInvocationLabelMajorTrueFamily W) := by
  let base :=
    verifierTransitionDispatchMuxInvocationLabelMajorTrueLabelFrames_computableInPolyTime
      W
  exact
    { tm := base.tm
      inputAlphabet := base.inputAlphabet
      outputAlphabet := base.outputAlphabet
      time := base.time
      outputsFun := fun input => by
        have run := base.outputsFun input
        simpa only [id_eq,
          (verifierTransitionDispatchMuxInvocationLabelMajorChannelFamily_encodings
            W input).2.2.1] using run }

private noncomputable def falseFamilyCompiler
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id
      encodeUnaryFrameMarkedRowFamily
      (verifierTransitionDispatchMuxInvocationLabelMajorFalseFamily W) := by
  let base :=
    verifierTransitionDispatchMuxInvocationLabelMajorFalseLabelFrames_computableInPolyTime
      W
  exact
    { tm := base.tm
      inputAlphabet := base.inputAlphabet
      outputAlphabet := base.outputAlphabet
      time := base.time
      outputsFun := fun input => by
        have run := base.outputsFun input
        simpa only [id_eq,
          (verifierTransitionDispatchMuxInvocationLabelMajorChannelFamily_encodings
            W input).2.2.2] using run }

private theorem selector_true_aligned
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    (verifierTransitionDispatchMuxInvocationLabelMajorSelectorFamily
      W input).rows.length =
      (verifierTransitionDispatchMuxInvocationLabelMajorTrueFamily
        W input).rows.length := by
  exact
    (verifierTransitionDispatchMuxInvocationDescriptorLabelPacketChannelFamily_rowAligned
      W input).2.1

private theorem coordinate_false_aligned
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    (verifierTransitionDispatchMuxInvocationLabelMajorCoordinateFamily
      W input).rows.length =
      (verifierTransitionDispatchMuxInvocationLabelMajorFalseFamily
        W input).rows.length := by
  have h :=
    verifierTransitionDispatchMuxInvocationDescriptorLabelPacketChannelFamily_rowAligned
      W input
  exact h.1.symm.trans h.2.2

private noncomputable def selectorTrueCompiler
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) := by
  letI : Fintype Γ := W.alphabetFintype
  exact
    PolyBuilder.UnaryFrameMarkedRowParallelInterleave.computableInPolyTime
      (selectorFamilyCompiler W) (trueFamilyCompiler W)
      (selector_true_aligned W)

private noncomputable def coordinateFalseCompiler
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) := by
  letI : Fintype Γ := W.alphabetFintype
  exact
    PolyBuilder.UnaryFrameMarkedRowParallelInterleave.computableInPolyTime
      (coordinateFamilyCompiler W) (falseFamilyCompiler W)
      (coordinate_false_aligned W)

private theorem pair_families_aligned
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    (PolyBuilder.UnaryFrameMarkedRowParallelInterleave.interleavedFamily
      (selector_true_aligned W) input).rows.length =
      (PolyBuilder.UnaryFrameMarkedRowParallelInterleave.interleavedFamily
        (coordinate_false_aligned W) input).rows.length := by
  have h :=
    verifierTransitionDispatchMuxInvocationDescriptorLabelPacketChannelFamily_rowAligned
      W input
  change
    (interleaveUnaryFrameMarkedRows
      (verifierTransitionDispatchMuxInvocationLabelMajorSelectorFamily
        W input).rows
      (verifierTransitionDispatchMuxInvocationLabelMajorTrueFamily
        W input).rows).length =
    (interleaveUnaryFrameMarkedRows
      (verifierTransitionDispatchMuxInvocationLabelMajorCoordinateFamily
        W input).rows
      (verifierTransitionDispatchMuxInvocationLabelMajorFalseFamily
        W input).rows).length
  rw [interleaveUnaryFrameMarkedRows_length_of_aligned _ _
    (selector_true_aligned W input)]
  rw [interleaveUnaryFrameMarkedRows_length_of_aligned _ _
    (coordinate_false_aligned W input)]
  exact congrArg (fun length => 2 * length) h.1

/-- The concrete three-interleaver output family. -/
noncomputable def
    verifierTransitionDispatchMuxInvocationLabelMajorPacketFamily
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : UnaryFrameMarkedRowFamily :=
  PolyBuilder.UnaryFrameMarkedRowParallelInterleave.interleavedFamily
    (pair_families_aligned W) input

private theorem nested_interleave_eq_four_way
    (selectors coordinates whenTrue whenFalse :
      List (List UnaryFrameSym))
    (hcoordinate : selectors.length = coordinates.length)
    (htrue : selectors.length = whenTrue.length)
    (hfalse : selectors.length = whenFalse.length) :
    interleaveUnaryFrameMarkedRows
        (interleaveUnaryFrameMarkedRows selectors whenTrue)
        (interleaveUnaryFrameMarkedRows coordinates whenFalse) =
      transitionDispatchMuxInvocationLabelPacketRowsFromChannels
        selectors coordinates whenTrue whenFalse := by
  induction selectors generalizing coordinates whenTrue whenFalse with
  | nil =>
      have hc : coordinates = [] :=
        List.eq_nil_of_length_eq_zero hcoordinate.symm
      have ht : whenTrue = [] :=
        List.eq_nil_of_length_eq_zero htrue.symm
      have hf : whenFalse = [] :=
        List.eq_nil_of_length_eq_zero hfalse.symm
      subst coordinates
      subst whenTrue
      subst whenFalse
      rfl
  | cons selector selectors ih =>
      cases coordinates with
      | nil => simp at hcoordinate
      | cons coordinate coordinates =>
          cases whenTrue with
          | nil => simp at htrue
          | cons truth whenTrue =>
              cases whenFalse with
              | nil => simp at hfalse
              | cons falsity whenFalse =>
                  simp only [List.length_cons] at hcoordinate htrue hfalse
                  simp only [interleaveUnaryFrameMarkedRows,
                    transitionDispatchMuxInvocationLabelPacketRowsFromChannels]
                  rw [ih coordinates whenTrue whenFalse (by omega)
                    (by omega) (by omega)]

/-- The three physical interleavers reconstruct the canonical four-row packet
encoding byte for byte. -/
theorem
    verifierTransitionDispatchMuxInvocationLabelMajorPacketFamily_encoding_eq
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    encodeUnaryFrameMarkedRowFamily
        (verifierTransitionDispatchMuxInvocationLabelMajorPacketFamily
          W input) =
      (verifierTransitionDispatchMuxInvocationAlignedViewFamily W input
        ).labelPacketFrames := by
  let channels :=
    verifierTransitionDispatchMuxInvocationDescriptorLabelPacketChannelFamily
      W input
  have haligned :=
    verifierTransitionDispatchMuxInvocationDescriptorLabelPacketChannelFamily_rowAligned
      W input
  have hrows := nested_interleave_eq_four_way
    channels.selectorRows channels.coordinateRows channels.trueRows
    channels.falseRows haligned.1 haligned.2.1 haligned.2.2
  have hreassembly :=
    verifierTransitionDispatchMuxInvocationDescriptorLabelPacketFrames_eq_channelReassembly
      W input
  have hcanonical :
      (verifierTransitionDispatchMuxInvocationAlignedViewFamily W input
        ).labelPacketFrames =
        verifierTransitionDispatchMuxInvocationDescriptorLabelPacketFrames
          W input := by
    unfold AlignedTransitionDispatchMuxInvocationViewFamily.labelPacketFrames
      verifierTransitionDispatchMuxInvocationAlignedViewFamily
      verifierTransitionDispatchMuxInvocationViews
    rw [encode_transitionDispatchMuxInvocationLabelPacketFamily]
    unfold
      verifierTransitionDispatchMuxInvocationDescriptorLabelPacketFrames
    exact List.flatMap_assoc
  rw [hcanonical, hreassembly]
  unfold verifierTransitionDispatchMuxInvocationLabelMajorPacketFamily
    PolyBuilder.UnaryFrameMarkedRowParallelInterleave.interleavedFamily
    UnaryFrameAlignedMarkedRowPair.interleaved
    encodeUnaryFrameMarkedRowFamily
  change
    (interleaveUnaryFrameMarkedRows
      (interleaveUnaryFrameMarkedRows channels.selectorRows channels.trueRows)
      (interleaveUnaryFrameMarkedRows channels.coordinateRows
        channels.falseRows)).flatMap (fun row => row ++ [.frameEnd]) = _
  simpa [encodeTransitionDispatchMuxInvocationLabelPacketChannelRows,
    channels] using congrArg
      (fun rows => rows.flatMap (fun row => row ++ [.frameEnd])) hrows

/-- Concrete raw-input compiler for the typed unprepared label-packet family.
-/
noncomputable def
    verifierTransitionDispatchMuxInvocationLabelMajorPacketFamily_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id
      AlignedTransitionDispatchMuxInvocationViewFamily.labelPacketFrames
      (verifierTransitionDispatchMuxInvocationAlignedViewFamily W) := by
  letI : Fintype Γ := W.alphabetFintype
  let pairCompiler :=
    PolyBuilder.UnaryFrameMarkedRowParallelInterleave.computableInPolyTime
      (selectorTrueCompiler W) (coordinateFalseCompiler W)
      (pair_families_aligned W)
  exact
    { tm := pairCompiler.tm
      inputAlphabet := pairCompiler.inputAlphabet
      outputAlphabet := pairCompiler.outputAlphabet
      time := pairCompiler.time
      outputsFun := fun input => by
        have run := pairCompiler.outputsFun input
        have run' : _root_.Turing.TM2OutputsInTime pairCompiler.tm
            (List.map pairCompiler.inputAlphabet.invFun input)
            (some (List.map pairCompiler.outputAlphabet.invFun
              (encodeUnaryFrameMarkedRowFamily
                (verifierTransitionDispatchMuxInvocationLabelMajorPacketFamily
                  W input))))
            (pairCompiler.time.eval input.length) := by
          simpa only [id_eq,
            verifierTransitionDispatchMuxInvocationLabelMajorPacketFamily]
            using run
        rw [
          verifierTransitionDispatchMuxInvocationLabelMajorPacketFamily_encoding_eq
            W input] at run'
        exact run' }

/-- The formerly conditional mux pipeline is now closed from the original
verifier input by the concrete label-major packet compiler. -/
noncomputable def
    verifierTransitionDispatchMuxInvocationFrames_labelMajor_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierTransitionDispatchMuxInvocationFrames W) :=
  verifierTransitionDispatchMuxInvocationFrames_computableInPolyTime_of_labelPacketCompiler
    W
    (verifierTransitionDispatchMuxInvocationLabelMajorPacketFamily_computableInPolyTime
      W)

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