Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_823e53f68cb2c3199f94901e

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_42934d19310e8c054b5508bb
import Definitions.Def_PricingWithTips3DM_3e4b5fb84cd3af16f2874725
import Definitions.Def_PricingWithTips3DM_a206cc095a01ca62b6c2f66a
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Concrete optional-conjunction input and gate source for verifier-input arms

Every published candidate length fits the tableau, so every optional entry is
present.  The generic all-present formatter converts the exact conjunction
frames into the input of the established optional-family gate controller.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- Arithmetic optional-frame family of all candidate certificate lengths. -/
def verifierInputArmOptionalFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List (Option AffineConjunctionFrame) :=
  List.ofFn fun arm :
      Fin (W.certificateBound.eval input.length + 1) =>
    some (verifierInputArmArithmeticFrame W input arm)

/-- Exact delimiter-bearing input of the optional conjunction controller. -/
def verifierInputArmOptionalInputTarget
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List UnaryFrameSym :=
  encodeUnaryFramePresentMarkedRowFamily
    (verifierInputArmArithmeticFrameFamily W input)

private theorem flatMap_two_ofFn
    {α γ β : Type} {count : Nat}
    (leftItems : Fin count → α) (rightItems : Fin count → γ)
    (left : α → List β) (right : γ → List β)
    (h : ∀ index, left (leftItems index) = right (rightItems index)) :
    (List.ofFn leftItems).flatMap left =
      (List.ofFn rightItems).flatMap right := by
  induction count with
  | zero => rfl
  | succ count ih =>
      rw [List.ofFn_succ, List.ofFn_succ]
      simp only [List.flatMap_cons]
      rw [h 0]
      exact congrArg (right (rightItems 0) ++ ·)
        (ih (fun index => leftItems index.succ)
          (fun index => rightItems index.succ)
          (fun index => h index.succ))

/-- The formatted marked rows are byte-for-byte the canonical all-present
optional conjunction-family encoding. -/
theorem verifierInputArmOptionalInputTarget_eq
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierInputArmOptionalInputTarget W input =
      encodeAffineOptionalConjunctionFamily
        (verifierInputArmOptionalFrames W input) := by
  unfold verifierInputArmOptionalInputTarget
    encodeUnaryFramePresentMarkedRowFamily
    verifierInputArmOptionalFrames
    encodeAffineOptionalConjunctionFamily
    encodeAffineOptionalConjunctionEntries
  rw [verifierInputArmArithmeticFrameFamily_rows]
  apply congrArg (fun stream => stream ++ [UnaryFrameSym.frameEnd])
  apply flatMap_two_ofFn
  intro arm
  unfold encodeAffineOptionalConjunctionEntry
    encodeAffineConjunctionFrame
  rfl

/-- One fixed polynomial-time TM2 constructs the exact optional-family input
from the raw verifier word. -/
noncomputable def
    verifierInputArmOptionalInputTarget_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierInputArmOptionalInputTarget W) := by
  letI : Fintype Γ := W.alphabetFintype
  let composed :=
    _root_.Turing.TM2Comp.TM2ComputableInPolyTime.comp_scratch
      (verifierInputArmArithmeticFrameFamily_computableInPolyTime W)
      unaryFrameMarkedRowPresent_computableInPolyTime
  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
        simpa only [Function.comp_def, id_eq,
          verifierInputArmOptionalInputTarget] using run }

/-- Literal circuit-byte stream of every candidate-length conjunction arm. -/
def verifierInputArmGateStream
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) : List CircuitSym :=
  affineOptionalConjunctionFamilyGateStream
    (verifierInputArmOptionalFrames W input)

/-- The arithmetic arm stream is exactly the arm phase of the canonical
semantic input-boundary script. -/
theorem verifierInputArmGateStream_eq_canonical
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) :
    verifierInputArmGateStream W input =
      affineOptionalConjunctionFamilyGateStream
        (verifierInputBoundaryScript W input).armFrames := by
  unfold verifierInputArmGateStream verifierInputArmOptionalFrames
  rw [verifierInputBoundaryScript_armFrames_eq_arithmetic]

/-- End-to-end concrete polynomial TM2 from the raw verifier word to every
serialized input-arm gate. -/
noncomputable def verifierInputArmGateStream_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierInputArmGateStream W) := by
  letI : Fintype Γ := W.alphabetFintype
  let source : _root_.Turing.TM2ComputableInPolyTime id
      encodeAffineOptionalConjunctionFamily
      (verifierInputArmOptionalFrames W) := by
    let raw := verifierInputArmOptionalInputTarget_computableInPolyTime W
    exact
      { tm := raw.tm
        inputAlphabet := raw.inputAlphabet
        outputAlphabet := raw.outputAlphabet
        time := raw.time
        outputsFun := fun input => by
          have run := raw.outputsFun input
          rw [verifierInputArmOptionalInputTarget_eq W input] at run
          simpa only [id_eq] using run }
  let composed :=
    _root_.Turing.TM2Comp.TM2ComputableInPolyTime.comp_scratch source
      affineOptionalConjunctionFamilyGateStream_computableInPolyTime
  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
        simpa only [Function.comp_def, id_eq,
          verifierInputArmGateStream] 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