Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_c101181cda2ded9319b876f7

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

/-!
# Fixed interpreter for length-prefixed transition descriptors

This module bridges the self-describing numeric row used by recursive syntax
to the existing four-row mux packet pipeline.  The bridge is generic over any
aligned mux-view family and reuses the verified dynamic splitter unchanged.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- Flatten the coordinate triples into the numeric row consumed by the
four-way splitter. -/
def TransitionDispatchMuxInvocationView.coordinateValues
    (view : TransitionDispatchMuxInvocationView) : List Nat :=
  view.coordinates.flatMap fun coordinate =>
    [coordinate.1, coordinate.2.1, coordinate.2.2]

@[simp] theorem TransitionDispatchMuxInvocationView.coordinateValues_length
    (view : TransitionDispatchMuxInvocationView) :
    view.coordinateValues.length = 3 * view.coordinates.length := by
  unfold TransitionDispatchMuxInvocationView.coordinateValues
  induction view.coordinates with
  | nil => rfl
  | cons coordinate rest ih =>
      simp only [List.flatMap_cons, List.length_append, List.length_cons,
        List.length_nil]
      omega

theorem TransitionDispatchMuxInvocationView.coordinateValues_encoding
    (view : TransitionDispatchMuxInvocationView) :
    encodeUnaryFrame view.coordinateValues =
      transitionDispatchMuxCoordinateRowFrames view.coordinates := by
  unfold TransitionDispatchMuxInvocationView.coordinateValues
    transitionDispatchMuxCoordinateRowFrames encodeUnaryFrame
  rw [List.flatMap_assoc]

/-- Package one aligned semantic mux view as a well-sized dynamic-splitter
packet. -/
def TransitionDispatchMuxInvocationView.lengthPrefixedPacket
    (view : TransitionDispatchMuxInvocationView)
    (haligned : view.RowAligned) :
    UnaryFrameLengthPrefixedFourWayPacket where
  width := view.coordinates.length
  selector := view.selector
  coordinates := view.coordinateValues
  whenTrue := view.whenTrue
  whenFalse := view.whenFalse
  coordinates_length := view.coordinateValues_length
  whenTrue_length := haligned.1.symm
  whenFalse_length := haligned.2.symm

theorem TransitionDispatchMuxInvocationView.lengthPrefixedPacket_sourceFrames
    (view : TransitionDispatchMuxInvocationView)
    (haligned : view.RowAligned) :
    (view.lengthPrefixedPacket haligned).sourceFrames =
      encodeUnaryFrame [view.coordinates.length] ++ view.numericDescriptorRow ++
        [UnaryFrameSym.frameEnd] := by
  unfold TransitionDispatchMuxInvocationView.lengthPrefixedPacket
    UnaryFrameLengthPrefixedFourWayPacket.sourceFrames
    encodeUnaryFrameLengthPrefixedFourWaySplitInput
  rw [view.coordinateValues_encoding]
  simp [TransitionDispatchMuxInvocationView.numericDescriptorRow,
    encodeUnaryFrame, List.append_assoc]

theorem TransitionDispatchMuxInvocationView.lengthPrefixedPacket_outputFrames
    (view : TransitionDispatchMuxInvocationView)
    (haligned : view.RowAligned) :
    (view.lengthPrefixedPacket haligned).outputFrames =
      view.labelPacketFrames := by
  simp [TransitionDispatchMuxInvocationView.lengthPrefixedPacket,
    UnaryFrameLengthPrefixedFourWayPacket.outputFrames,
    encodeUnaryFrameLengthPrefixedFourWaySplitOutput,
    TransitionDispatchMuxInvocationView.labelPacketFrames,
    view.coordinateValues_encoding, List.append_assoc]

/-- Turn a proof-carrying aligned list into a dynamic-splitter packet list. -/
def transitionDispatchMuxInvocationLengthPrefixedPacketsFrom :
    (views : List TransitionDispatchMuxInvocationView) →
      (∀ view ∈ views, view.RowAligned) →
        List UnaryFrameLengthPrefixedFourWayPacket
  | [], _ => []
  | view :: rest, haligned =>
      view.lengthPrefixedPacket (haligned view (by simp)) ::
        transitionDispatchMuxInvocationLengthPrefixedPacketsFrom rest
          (fun item hitem => haligned item (by simp [hitem]))

def AlignedTransitionDispatchMuxInvocationViewFamily.lengthPrefixedPackets
    (family : AlignedTransitionDispatchMuxInvocationViewFamily) :
    List UnaryFrameLengthPrefixedFourWayPacket :=
  transitionDispatchMuxInvocationLengthPrefixedPacketsFrom family.views
    family.rowAligned

/-- Literal concatenation of all self-describing numeric packets. -/
def AlignedTransitionDispatchMuxInvocationViewFamily.lengthPrefixedDescriptorFrames
    (family : AlignedTransitionDispatchMuxInvocationViewFamily) :
    List UnaryFrameSym :=
  encodeUnaryFrameLengthPrefixedFourWayPacketFamily
    family.lengthPrefixedPackets

private theorem lengthPrefixedPacketsFrom_sourceFrames
    (views : List TransitionDispatchMuxInvocationView)
    (haligned : ∀ view ∈ views, view.RowAligned) :
    encodeUnaryFrameLengthPrefixedFourWayPacketFamily
        (transitionDispatchMuxInvocationLengthPrefixedPacketsFrom views
          haligned) =
      views.flatMap fun view =>
        encodeUnaryFrame [view.coordinates.length] ++ view.numericDescriptorRow ++
          [UnaryFrameSym.frameEnd] := by
  induction views with
  | nil => rfl
  | cons view rest ih =>
      simp only [transitionDispatchMuxInvocationLengthPrefixedPacketsFrom,
        encodeUnaryFrameLengthPrefixedFourWayPacketFamily, List.flatMap_cons]
      rw [view.lengthPrefixedPacket_sourceFrames]
      have ih' := ih (fun item hitem => haligned item (by simp [hitem]))
      change List.flatMap UnaryFrameLengthPrefixedFourWayPacket.sourceFrames
          (transitionDispatchMuxInvocationLengthPrefixedPacketsFrom rest _) = _
        at ih'
      rw [ih']

private theorem lengthPrefixedPacketsFrom_outputFrames
    (views : List TransitionDispatchMuxInvocationView)
    (haligned : ∀ view ∈ views, view.RowAligned) :
    unaryFrameLengthPrefixedFourWayPacketFamilyOutput
        (transitionDispatchMuxInvocationLengthPrefixedPacketsFrom views
          haligned) =
      views.flatMap TransitionDispatchMuxInvocationView.labelPacketFrames := by
  induction views with
  | nil => rfl
  | cons view rest ih =>
      simp only [transitionDispatchMuxInvocationLengthPrefixedPacketsFrom,
        unaryFrameLengthPrefixedFourWayPacketFamilyOutput, List.flatMap_cons]
      rw [view.lengthPrefixedPacket_outputFrames]
      have ih' := ih (fun item hitem => haligned item (by simp [hitem]))
      change List.flatMap UnaryFrameLengthPrefixedFourWayPacket.outputFrames
          (transitionDispatchMuxInvocationLengthPrefixedPacketsFrom rest _) = _
        at ih'
      rw [ih']

theorem AlignedTransitionDispatchMuxInvocationViewFamily.lengthPrefixedDescriptorFrames_eq
    (family : AlignedTransitionDispatchMuxInvocationViewFamily) :
    family.lengthPrefixedDescriptorFrames =
      family.views.flatMap fun view =>
        encodeUnaryFrame [view.coordinates.length] ++ view.numericDescriptorRow ++
          [UnaryFrameSym.frameEnd] := by
  exact lengthPrefixedPacketsFrom_sourceFrames family.views family.rowAligned

theorem AlignedTransitionDispatchMuxInvocationViewFamily.lengthPrefixedPackets_output
    (family : AlignedTransitionDispatchMuxInvocationViewFamily) :
    unaryFrameLengthPrefixedFourWayPacketFamilyOutput
        family.lengthPrefixedPackets = family.labelPacketFrames := by
  unfold AlignedTransitionDispatchMuxInvocationViewFamily.labelPacketFrames
  rw [encode_transitionDispatchMuxInvocationLabelPacketFamily]
  exact lengthPrefixedPacketsFrom_outputFrames family.views family.rowAligned

/-- The dynamic splitter is a fixed polynomial-time interpreter from aligned
length-prefixed numeric descriptors to the existing four-row packet format. -/
noncomputable def
    transitionDispatchMuxInvocationLengthPrefixedDescriptorInterpreter_computableInPolyTime :
    _root_.Turing.TM2ComputableInPolyTime
      AlignedTransitionDispatchMuxInvocationViewFamily.lengthPrefixedDescriptorFrames
      AlignedTransitionDispatchMuxInvocationViewFamily.labelPacketFrames id := by
  let generic :=
    unaryFrameLengthPrefixedFourWayPacketFamilyOutput_computableInPolyTime
  exact
    { tm := generic.tm
      inputAlphabet := generic.inputAlphabet
      outputAlphabet := generic.outputAlphabet
      time := generic.time
      outputsFun := fun family => by
        have run := generic.outputsFun family.lengthPrefixedPackets
        simpa only [id_eq,
          AlignedTransitionDispatchMuxInvocationViewFamily.lengthPrefixedDescriptorFrames,
          family.lengthPrefixedPackets_output] 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