Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_7056c2685e5712b969302bae

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_958a644893103d57ea9b6b2a
import Definitions.Def_PricingWithTips3DM_645fa74d60687a6229a5303d
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Typed raw-input row families for branch-ending statement results

The branch-route source emits one complete marked row per transition seed.
This module packages those rows behind the same typed family interface used
by normalized linear results.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

private theorem branchRoute_encodeUnaryFrame_frameEnd_free
    (values : List Nat) :
    ∀ symbol ∈ encodeUnaryFrame values, symbol ≠ UnaryFrameSym.frameEnd := by
  intro symbol hsymbol
  induction values with
  | nil => simp [encodeUnaryFrame] at hsymbol
  | cons value values ih =>
      simp only [encodeUnaryFrame, List.flatMap_cons] at hsymbol
      rw [List.mem_append] at hsymbol
      rcases hsymbol with hhead | htail
      · unfold encodeUnaryFrameBlock at hhead
        rw [List.mem_append] at hhead
        rcases hhead with htick | hseparator
        · have : symbol = UnaryFrameSym.tick :=
            List.eq_of_mem_replicate htick
          subst symbol
          decide
        · have : symbol = UnaryFrameSym.separator := by
            simpa using hseparator
          subst symbol
          decide
      · exact ih htail

/-- Semantic branch-route rows of one fixed statement context and mux
offset. -/
noncomputable def verifierTransitionStmtBranchRouteFamily
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (labelOffset : TransitionAffineNat)
    (context : TransitionStmtAffineContext W.machine.tm)
    (offset : TransitionAffineNat)
    (input : List Γ) : UnaryFrameMarkedRowFamily :=
  { rows := (verifierTransitionRowSeeds W input).map fun seed =>
      encodeUnaryFrame
        (transitionStmtBranchRouteValues W.machine.tm seed labelOffset
          context offset)
    frameEnd_free := by
      intro row hrow symbol hsymbol
      rw [List.mem_map] at hrow
      rcases hrow with ⟨seed, hseed, rfl⟩
      exact branchRoute_encodeUnaryFrame_frameEnd_free _ symbol hsymbol }

/-- The typed family encoding is exactly the concrete affine-segment source
stream. -/
theorem verifierTransitionStmtBranchRouteFamily_encoding_eq
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (input : List Γ) (labelOffset : TransitionAffineNat)
    (context : TransitionStmtAffineContext W.machine.tm)
    (offset : TransitionAffineNat) :
    encodeUnaryFrameMarkedRowFamily
        (verifierTransitionStmtBranchRouteFamily W labelOffset context offset
          input) =
      verifierTransitionStmtBranchRouteFrames W labelOffset context offset
        input := by
  rw [verifierTransitionStmtBranchRouteFrames_eq]
  unfold encodeUnaryFrameMarkedRowFamily
    verifierTransitionStmtBranchRouteFamily
  simp [List.flatMap_map]

/-- The typed semantic branch-route family is generated by a concrete fixed
polynomial-time TM2 from the original verifier word. -/
noncomputable def
    verifierTransitionStmtBranchRouteFamily_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (labelOffset : TransitionAffineNat)
    (context : TransitionStmtAffineContext W.machine.tm)
    (offset : TransitionAffineNat) :
    _root_.Turing.TM2ComputableInPolyTime id
      encodeUnaryFrameMarkedRowFamily
      (verifierTransitionStmtBranchRouteFamily W labelOffset context offset) := by
  let source :=
    verifierTransitionStmtBranchRouteFrames_computableInPolyTime W
      labelOffset context offset
  exact
    { tm := source.tm
      inputAlphabet := source.inputAlphabet
      outputAlphabet := source.outputAlphabet
      time := source.time
      outputsFun := fun input => by
        simpa only [id_eq,
          verifierTransitionStmtBranchRouteFamily_encoding_eq W input
            labelOffset context offset] using source.outputsFun input }

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