Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_bef6aff283c342b69c7dc099

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_23147177f99a35f5d19cebcb
import Mathlib.Tactic
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Polynomial bounds for dispatch-mux packet assembly

The exact execution formulas are bounded here by the literal size of the
prepared four-row packet stream.  In particular, replaying the selector once
per coordinate is charged quadratically to the explicit selector and row
width already present in that stream.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- Literal size of one prepared four-row packet. -/
@[simp] theorem
    TransitionDispatchMuxInvocationView.preparedLabelPacketFrames_length
    (view : TransitionDispatchMuxInvocationView) :
    view.preparedLabelPacketFrames.length =
      view.selector +
        (transitionDispatchMuxCoordinateRowFrames
          view.coordinates).length +
        (encodeUnaryFrame view.whenTrue).length +
        (encodeUnaryFrame view.whenFalse).length + 5 := by
  unfold TransitionDispatchMuxInvocationView.preparedLabelPacketFrames
  simp only [List.length_append, List.length_cons, List.length_nil,
    List.length_reverse, encodeUnaryFrame_length]
  simp
  omega

/-- The coordinate zipper and its terminal case are quadratic in the literal
four-row packet measure. -/
theorem transitionDispatchMuxInvocationLabelPacketAssemblerRowsSteps_le
    (selector : Nat) (first : Bool)
    (coordinates : List (Nat × Nat × Nat))
    (whenTrue whenFalse : List Nat)
    (htrue : coordinates.length = whenTrue.length)
    (hfalse : coordinates.length = whenFalse.length) :
    transitionDispatchMuxInvocationLabelPacketAssemblerRowsSteps selector
        first
        (transitionDispatchMuxInvocationLabelPacketAssemblerFrames selector
          coordinates whenTrue whenFalse) ≤
      100 * (selector +
        (transitionDispatchMuxCoordinateRowFrames coordinates).length +
        (encodeUnaryFrame whenTrue).length +
        (encodeUnaryFrame whenFalse).length + 5) ^ 2 := by
  induction coordinates generalizing first whenTrue whenFalse with
  | nil =>
      have htrueNil : whenTrue = [] := by simpa using htrue.symm
      have hfalseNil : whenFalse = [] := by simpa using hfalse.symm
      subst whenTrue
      subst whenFalse
      cases first <;>
        simp [transitionDispatchMuxInvocationLabelPacketAssemblerFrames,
          TransitionDispatchMuxInvocationView.frames,
          transitionDispatchMuxInvocationLabelPacketAssemblerRowsSteps,
          transitionDispatchMuxInvocationLabelPacketAssemblerEmptySteps,
          transitionDispatchMuxInvocationLabelPacketAssemblerFinishSteps,
          transitionDispatchMuxCoordinateRowFrames, encodeUnaryFrame] <;>
        nlinarith
  | cons coordinate coordinates ih =>
      cases whenTrue with
      | nil => simp at htrue
      | cons whenTrue whenTrueTail =>
          cases whenFalse with
          | nil => simp at hfalse
          | cons whenFalse whenFalseTail =>
              have htrueTail : coordinates.length = whenTrueTail.length := by
                simpa using Nat.succ.inj htrue
              have hfalseTail : coordinates.length = whenFalseTail.length := by
                simpa using Nat.succ.inj hfalse
              let frame : AffineMuxFinPairFrame :=
                { whenTrue := whenTrue
                  whenFalse := whenFalse
                  selector := selector
                  selectorNot := coordinate.1
                  trueArm := coordinate.2.1
                  falseArm := coordinate.2.2 }
              let tailMeasure := selector +
                (transitionDispatchMuxCoordinateRowFrames
                  coordinates).length +
                (encodeUnaryFrame whenTrueTail).length +
                (encodeUnaryFrame whenFalseTail).length + 5
              let headMeasure := coordinate.1 + coordinate.2.1 +
                coordinate.2.2 + whenTrue + whenFalse + 5
              have htail := ih (first := false)
                (whenTrue := whenTrueTail) (whenFalse := whenFalseTail)
                htrueTail hfalseTail
              change
                transitionDispatchMuxInvocationLabelPacketAssemblerRowsSteps
                    selector false
                    (transitionDispatchMuxInvocationLabelPacketAssemblerFrames
                      selector coordinates whenTrueTail whenFalseTail) ≤
                  100 * tailMeasure ^ 2 at htail
              have htailPos : 1 ≤ tailMeasure := by
                simp [tailMeasure]
              have hheadPos : 1 ≤ headMeasure := by
                simp [headMeasure]
              have hselector : selector ≤ tailMeasure := by
                dsimp [tailMeasure]
                omega
              have hstep :
                  transitionDispatchMuxInvocationLabelPacketAssemblerCoordinateSteps
                      selector frame ≤
                    10 * headMeasure * tailMeasure := by
                dsimp [frame,
                  headMeasure, tailMeasure,
                  transitionDispatchMuxInvocationLabelPacketAssemblerCoordinateSteps]
                nlinarith
              have hmeasure :
                  selector +
                      (transitionDispatchMuxCoordinateRowFrames
                        (coordinate :: coordinates)).length +
                      (encodeUnaryFrame
                        (whenTrue :: whenTrueTail)).length +
                      (encodeUnaryFrame
                        (whenFalse :: whenFalseTail)).length + 5 =
                    tailMeasure + headMeasure := by
                simp [tailMeasure, headMeasure,
                  transitionDispatchMuxCoordinateRowFrames,
                  encodeUnaryFrame, encodeUnaryFrameBlock]
                omega
              rw [hmeasure]
              simp only [
                transitionDispatchMuxInvocationLabelPacketAssemblerFrames,
                TransitionDispatchMuxInvocationView.frames, List.zipWith3,
                transitionDispatchMuxInvocationLabelPacketAssemblerRowsSteps]
              change
                transitionDispatchMuxInvocationLabelPacketAssemblerCoordinateSteps
                    selector frame +
                    transitionDispatchMuxInvocationLabelPacketAssemblerRowsSteps
                      selector false
                      (transitionDispatchMuxInvocationLabelPacketAssemblerFrames
                        selector coordinates whenTrueTail whenFalseTail) ≤
                  100 * (tailMeasure + headMeasure) ^ 2
              nlinarith [Nat.zero_le tailMeasure, Nat.zero_le headMeasure]

/-- Loading plus assembling one aligned label is quadratic in its prepared
packet length. -/
theorem transitionDispatchMuxInvocationLabelPacketAssemblerLabelSteps_le
    (view : TransitionDispatchMuxInvocationView)
    (haligned : view.RowAligned) :
    transitionDispatchMuxInvocationLabelPacketAssemblerLoadSteps view +
        transitionDispatchMuxInvocationLabelPacketAssemblerRowsSteps
          view.selector true view.frames ≤
      110 * view.preparedLabelPacketFrames.length ^ 2 := by
  rcases haligned with ⟨htrue, hfalse⟩
  have hrows :=
    transitionDispatchMuxInvocationLabelPacketAssemblerRowsSteps_le
      view.selector true view.coordinates view.whenTrue view.whenFalse
      htrue hfalse
  have hframes :
      transitionDispatchMuxInvocationLabelPacketAssemblerFrames view.selector
          view.coordinates view.whenTrue view.whenFalse = view.frames := by
    rcases view
    rfl
  rw [hframes] at hrows
  rw [← view.preparedLabelPacketFrames_length] at hrows
  have hpacket : 5 ≤ view.preparedLabelPacketFrames.length := by
    simp
  have hload :
      transitionDispatchMuxInvocationLabelPacketAssemblerLoadSteps view ≤
        10 * view.preparedLabelPacketFrames.length ^ 2 := by
    unfold transitionDispatchMuxInvocationLabelPacketAssemblerLoadSteps
    have hcoord :
        (transitionDispatchMuxCoordinateRowFrames
          view.coordinates).length ≤
          view.preparedLabelPacketFrames.length := by
      rw [view.preparedLabelPacketFrames_length]
      omega
    have htrueLength :
        (encodeUnaryFrame view.whenTrue).length ≤
          view.preparedLabelPacketFrames.length := by
      rw [view.preparedLabelPacketFrames_length]
      omega
    have hselector :
        view.selector ≤ view.preparedLabelPacketFrames.length := by
      rw [view.preparedLabelPacketFrames_length]
      omega
    nlinarith
  nlinarith

/-- The whole aligned label family is quadratic in the concatenated prepared
packet stream. -/
theorem transitionDispatchMuxInvocationLabelPacketAssemblerFamilySteps_le
    (views : List TransitionDispatchMuxInvocationView)
    (haligned : ∀ view ∈ views, view.RowAligned) :
    transitionDispatchMuxInvocationLabelPacketAssemblerFamilySteps views ≤
      110 * (views.flatMap
        TransitionDispatchMuxInvocationView.preparedLabelPacketFrames
        ).length ^ 2 := by
  induction views with
  | nil => simp [transitionDispatchMuxInvocationLabelPacketAssemblerFamilySteps]
  | cons view views ih =>
      have hview : view.RowAligned := haligned view (by simp)
      have hviews : ∀ other ∈ views, other.RowAligned := by
        intro other hother
        exact haligned other (by simp [hother])
      have hone :=
        transitionDispatchMuxInvocationLabelPacketAssemblerLabelSteps_le
          view hview
      have hrest := ih hviews
      simp only [transitionDispatchMuxInvocationLabelPacketAssemblerFamilySteps]
        at hrest
      simp only [transitionDispatchMuxInvocationLabelPacketAssemblerFamilySteps,
        List.map_cons, List.sum_cons, List.flatMap_cons,
        List.length_append]
      nlinarith [Nat.zero_le view.preparedLabelPacketFrames.length,
        Nat.zero_le (views.flatMap
          TransitionDispatchMuxInvocationView.preparedLabelPacketFrames).length]

/-- On the real verifier stream, the complete assembler execution (including
halt) has a uniform quadratic bound in its literal prepared input length. -/
theorem verifierTransitionDispatchMuxInvocationLabelPacketAssemblerSteps_le
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierTransitionDispatchMuxInvocationLabelPacketAssemblerSteps W input ≤
      110 *
        (verifierTransitionDispatchMuxInvocationDescriptorPreparedLabelPacketFrames
          W input).length ^ 2 + 2 := by
  let views := verifierTransitionDispatchMuxInvocationViews W input
  have haligned : ∀ view ∈ views, view.RowAligned := by
    simpa [views] using
      verifierTransitionDispatchMuxInvocationViews_rowAligned W input
  have hbound :=
    transitionDispatchMuxInvocationLabelPacketAssemblerFamilySteps_le
      views haligned
  have hprepared :=
    verifierTransitionDispatchMuxInvocationDescriptorPreparedLabelPacketFrames_eq
      W input
  change
    transitionDispatchMuxInvocationLabelPacketAssemblerFamilySteps
          (verifierTransitionDispatchMuxInvocationViews W input) + 2 ≤
      110 *
        (verifierTransitionDispatchMuxInvocationDescriptorPreparedLabelPacketFrames
          W input).length ^ 2 + 2
  apply Nat.add_le_add_right
  rw [hprepared]
  simpa [views, verifierTransitionDispatchMuxInvocationViews] using hbound

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