Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.CookLevin.Circuitization.GeneratorValidityRowInputCompiler.Part12

Definition
PricingWithTips3DM_af2d95bc038028b6e710a3e2Part12

by qmaai2907271020 · Oct 22, 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_af2d95bc038028b6e710a3e2Part11
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- Typed view for rewriting only the fixed prefix of the retained second
row, while preserving the canonical one-hot leading segment. -/
noncomputable def verifierValidityRowLeadingFixedPrefixFamily
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    UnaryFrameLeadingSegmentFixedPrefixFamily
      (arithmeticValidityRowFixedOperandDelimiters W.machine.tm) :=
  { rows := (verifierValidityRowSeeds W input).map fun seed =>
      { leading := .tick :: encodeAffineExactlyOneFamily
          (validityRowSeedOneHotFrames W.machine.tm seed)
        values := arithmeticValidityRowFixedOperandValues W.machine.tm
          seed.height seed.start seed.rowBase
        payload := encodeAffineExactlyOneCompactFamily
          (validityRowSeedOneHotFrames W.machine.tm seed) }
    values_lengths := by
      intro row hrow
      rw [List.mem_map] at hrow
      rcases hrow with ⟨seed, hseed, rfl⟩
      exact arithmeticValidityRowFixedOperandValues_length
        W.machine.tm seed.height seed.start seed.rowBase
    leading_frameEnd_free := by
      intro row hrow symbol hsymbol
      rw [List.mem_map] at hrow
      rcases hrow with ⟨seed, hseed, rfl⟩
      simp only [List.mem_cons] at hsymbol
      rcases hsymbol with rfl | hfamily
      · simp
      · exact inputCompiler_exactlyOneFamily_no_frameEnd _ symbol hfamily
    payload_frameEnd_free := by
      intro row hrow symbol hsymbol
      rw [List.mem_map] at hrow
      rcases hrow with ⟨seed, hseed, rfl⟩
      exact inputCompiler_compactFamily_no_frameEnd _ symbol hsymbol }

/-- The typed fixed-prefix input is exactly the expanded-prefix stream. -/
theorem verifierValidityRowLeadingFixedPrefixFamily_encoding_eq
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    encodeUnaryFrameLeadingSegmentFixedPrefixInput
        (verifierValidityRowLeadingFixedPrefixFamily W input) =
      verifierValidityRowExpandedPrefixPayloadFrames W input := by
  rw [verifierValidityRowExpandedPrefixPayloadFrames_eq_rows]
  unfold encodeUnaryFrameLeadingSegmentFixedPrefixInput
    verifierValidityRowLeadingFixedPrefixFamily
  rw [List.flatMap_map]
  simp [List.append_assoc]

/-- Canonical one-hot prefixes followed by delimiter-materialized fixed
halted/tail operands and the retained compact one-hot suffix. -/
noncomputable def verifierValidityRowFixedPrefixMaterializedFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List UnaryFrameSym :=
  encodeUnaryFrameLeadingSegmentFixedPrefixOutput
    (verifierValidityRowLeadingFixedPrefixFamily W input)

/-- Exact row-major semantics after the fixed delimiter rewrite. -/
theorem verifierValidityRowFixedPrefixMaterializedFrames_eq_rows
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierValidityRowFixedPrefixMaterializedFrames W input =
      (verifierValidityRowSeeds W input).flatMap fun seed =>
        .tick ::
          (encodeAffineExactlyOneFamily
              (validityRowSeedOneHotFrames W.machine.tm seed) ++
            .frameEnd ::
              (encodeUnaryFrameWithFixedDelimiters
                  (arithmeticValidityRowFixedOperandValues W.machine.tm
                    seed.height seed.start seed.rowBase)
                  (arithmeticValidityRowFixedOperandDelimiters W.machine.tm) ++
                encodeAffineExactlyOneCompactFamily
                  (validityRowSeedOneHotFrames W.machine.tm seed) ++
                [.frameEnd])) := by
  unfold verifierValidityRowFixedPrefixMaterializedFrames
    encodeUnaryFrameLeadingSegmentFixedPrefixOutput
    verifierValidityRowLeadingFixedPrefixFamily
  rw [List.flatMap_map]
  simp [List.append_assoc]

/-- The materialized second-row prefix exposes the exact halted boundary and
the complete established tail-prefix delimiter table. -/
theorem verifierValidityRowFixedPrefixMaterializedFrames_eq_explicit
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierValidityRowFixedPrefixMaterializedFrames W input =
      (verifierValidityRowSeeds W input).flatMap fun seed =>
        .tick ::
          (encodeAffineExactlyOneFamily
              (validityRowSeedOneHotFrames W.machine.tm seed) ++
            .frameEnd ::
              (encodeUnaryFrame
                    [ arithmeticHaltedMatchStart W.machine.tm
                        seed.height seed.start,
                      seed.rowBase,
                      arithmeticNoneLabelWire W.machine.tm seed.rowBase ] ++
                [.frameEnd] ++
                encodeUnaryFrameWithFixedDelimiters
                  (arithmeticValidityTailFixedOperandValues W.machine.tm
                    seed.height seed.start seed.rowBase)
                  (arithmeticValidityTailFixedOperandDelimiters W.machine.tm) ++
                encodeAffineExactlyOneCompactFamily
                  (validityRowSeedOneHotFrames W.machine.tm seed) ++
                [.frameEnd])) := by
  rw [verifierValidityRowFixedPrefixMaterializedFrames_eq_rows]
  generalize verifierValidityRowSeeds W input = seeds
  induction seeds with
  | nil => rfl
  | cons seed rest ih =>
      simp only [List.flatMap_cons]
      rw [arithmeticValidityRowFixedEncoding_eq, ih]

/-- The raw verifier word computes the delimiter-materialized row stream by
one fixed polynomial-time composition. -/
noncomputable def
    verifierValidityRowFixedPrefixMaterializedFrames_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierValidityRowFixedPrefixMaterializedFrames W) := by
  let expandedSource :=
    verifierValidityRowExpandedPrefixPayloadFrames_computableInPolyTime W
  let typedExpandedSource :
      _root_.Turing.TM2ComputableInPolyTime id
        encodeUnaryFrameLeadingSegmentFixedPrefixInput
        (verifierValidityRowLeadingFixedPrefixFamily W) :=
    { tm := expandedSource.tm
      inputAlphabet := expandedSource.inputAlphabet
      outputAlphabet := expandedSource.outputAlphabet
      time := expandedSource.time
      outputsFun := fun input => by
        simpa only [id_eq,
          verifierValidityRowLeadingFixedPrefixFamily_encoding_eq W input]
          using expandedSource.outputsFun input }
  let spliceSource :=
    unaryFrameLeadingSegmentFixedPrefix_computableInPolyTime
      (arithmeticValidityRowFixedOperandDelimiters W.machine.tm)
  let typedSpliceSource :
      _root_.Turing.TM2ComputableInPolyTime
        encodeUnaryFrameLeadingSegmentFixedPrefixInput id
        (fun family : UnaryFrameLeadingSegmentFixedPrefixFamily
            (arithmeticValidityRowFixedOperandDelimiters W.machine.tm) =>
          rewriteUnaryFrameLeadingSegmentFixedPrefix
            (arithmeticValidityRowFixedOperandDelimiters W.machine.tm)
            (encodeUnaryFrameLeadingSegmentFixedPrefixInput family)) :=
    { tm := spliceSource.tm
      inputAlphabet := spliceSource.inputAlphabet
      outputAlphabet := spliceSource.outputAlphabet
      time := spliceSource.time
      outputsFun := fun family => by
        simpa only [id_eq] using spliceSource.outputsFun
          (encodeUnaryFrameLeadingSegmentFixedPrefixInput family) }
  let composed :=
    _root_.Turing.TM2Comp.TM2ComputableInPolyTime.comp_scratch
      typedExpandedSource typedSpliceSource
  let result := Classical.choice composed
  exact
    { tm := result.tm
      inputAlphabet := result.inputAlphabet
      outputAlphabet := result.outputAlphabet
      time := result.time
      outputsFun := fun input => by
        have run := result.outputsFun input
        simp only [Function.comp_apply, id_eq] at run
        rw [rewriteUnaryFrameLeadingSegmentFixedPrefix_family
          (arithmeticValidityRowFixedOperandDelimiters W.machine.tm)
          (verifierValidityRowLeadingFixedPrefixFamily W input)
          (arithmeticValidityRowFixedOperandDelimiters_nonempty W.machine.tm)]
          at run
        simpa only [id_eq,
          verifierValidityRowFixedPrefixMaterializedFrames]
          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