Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_f60b39e2dfaffb7ad0a09657

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

/-!
# Complete affine one-hot-predicate statement phases

A Boolean query over one-hot state wires is a single canonical disjunction of
the verifier-fixed true fiber.  This module constructs that fiber and its OR
frames symbolically, proves that affine evaluation recovers the existing
semantic phase, and emits the phase tag and payload together from the original
verifier input.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- Affine source forms selected by the true fiber of a fixed predicate. -/
def transitionOneHotPredicateWireForms {n : Nat}
    (source : Fin n → AffineUnaryTripleForm) (f : Fin n → Bool) :
    List AffineUnaryTripleForm :=
  (oneHotTruePreimage f).toList.map source

/-- Evaluation of the symbolic true fiber is the literal operand list used by
the semantic one-hot-predicate circuit. -/
theorem transitionOneHotPredicateWireForms_eval {n : Nat}
    (source : Fin n → AffineUnaryTripleForm) (f : Fin n → Bool)
    (seed : AffineUnaryTripleSeed) :
    affineUnaryTripleMap (transitionOneHotPredicateWireForms source f) seed =
      oneHotPredicateWires
        (fun i => affineUnaryTripleFormValue (source i) seed) f := by
  simp [transitionOneHotPredicateWireForms, oneHotPredicateWires,
    affineUnaryTripleMap, List.map_map, Function.comp_def]

/-- Symbolic canonical OR frames for one fixed one-hot predicate. -/
def transitionAffineOneHotPredicateCanonicalFrames {n : Nat}
    (start : AffineUnaryTripleForm)
    (source : Fin n → AffineUnaryTripleForm) (f : Fin n → Bool) :
    List TransitionAffineOrPairForm :=
  transitionAffineOrCanonicalFrameForms start
    (transitionOneHotPredicateWireForms source f)

/-- Evaluating the symbolic frames gives the established canonical predicate
phase, including the all-false empty-fiber case. -/
theorem transitionAffineOneHotPredicateCanonicalFrames_eval {n : Nat}
    (start : AffineUnaryTripleForm)
    (source : Fin n → AffineUnaryTripleForm) (f : Fin n → Bool)
    (seed : AffineUnaryTripleSeed) :
    (transitionAffineOneHotPredicateCanonicalFrames start source f).map
        (fun frame => frame.eval seed) =
      affineOneHotPredicateCanonicalFrames
        (affineUnaryTripleFormValue start seed)
        (fun i => affineUnaryTripleFormValue (source i) seed) f := by
  unfold transitionAffineOneHotPredicateCanonicalFrames
    affineOneHotPredicateCanonicalFrames
  rw [transitionAffineOrCanonicalFrameForms_eval]
  congr 1
  exact transitionOneHotPredicateWireForms_eval source f seed

/-- Affine fields for a complete tagged predicate phase. -/
def transitionAffineOneHotPredicatePhaseFieldForms {n : Nat}
    (start : AffineUnaryTripleForm)
    (source : Fin n → AffineUnaryTripleForm) (f : Fin n → Bool) :
    List AffineUnaryTripleForm :=
  [transitionZeroForm, transitionZeroForm, transitionZeroForm] ++
    transitionAffineOrFieldForms
      (transitionAffineOneHotPredicateCanonicalFrames start source f)

/-- Fixed delimiter table for a complete tagged predicate phase. -/
def transitionAffineOneHotPredicatePhaseDelimiters {n : Nat}
    (start : AffineUnaryTripleForm)
    (source : Fin n → AffineUnaryTripleForm) (f : Fin n → Bool) :
    List UnaryFrameSym :=
  [.tick, .tick, .frameEnd] ++
    transitionAffineOrDelimiters
      (transitionAffineOneHotPredicateCanonicalFrames start source f)

theorem transitionAffineOneHotPredicatePhase_lengths {n : Nat}
    (start : AffineUnaryTripleForm)
    (source : Fin n → AffineUnaryTripleForm) (f : Fin n → Bool) :
    (transitionAffineOneHotPredicatePhaseFieldForms start source f).length =
      (transitionAffineOneHotPredicatePhaseDelimiters start source f).length := by
  simp [transitionAffineOneHotPredicatePhaseFieldForms,
    transitionAffineOneHotPredicatePhaseDelimiters]

theorem transitionAffineOneHotPredicatePhaseDelimiters_nonempty {n : Nat}
    (start : AffineUnaryTripleForm)
    (source : Fin n → AffineUnaryTripleForm) (f : Fin n → Bool) :
    0 <
      (transitionAffineOneHotPredicatePhaseDelimiters start source f).length := by
  simp [transitionAffineOneHotPredicatePhaseDelimiters]

/-- Fixed-delimiter evaluation is exactly the official complete predicate
controller phase, tag included. -/
theorem transitionAffineOneHotPredicatePhase_fixed_encoding {n : Nat}
    (start : AffineUnaryTripleForm)
    (source : Fin n → AffineUnaryTripleForm) (f : Fin n → Bool)
    (seed : AffineUnaryTripleSeed) :
    encodeUnaryFrameWithFixedDelimiters
        (affineUnaryTripleMap
          (transitionAffineOneHotPredicatePhaseFieldForms start source f)
          seed)
        (transitionAffineOneHotPredicatePhaseDelimiters start source f) =
      encodeAffineStmtControllerPhase
        (.oneHotPredicate
          ((transitionAffineOneHotPredicateCanonicalFrames start source f).map
            fun frame => frame.eval seed)) := by
  rw [show transitionAffineOneHotPredicatePhaseFieldForms start source f =
      [transitionZeroForm, transitionZeroForm, transitionZeroForm] ++
        transitionAffineOrFieldForms
          (transitionAffineOneHotPredicateCanonicalFrames start source f) by
        rfl]
  rw [affineUnaryTripleMap, List.map_append]
  rw [show transitionAffineOneHotPredicatePhaseDelimiters start source f =
      [.tick, .tick, .frameEnd] ++
        transitionAffineOrDelimiters
          (transitionAffineOneHotPredicateCanonicalFrames start source f) by
        rfl]
  rw [encodeUnaryFrameWithFixedDelimiters_append _ _ _ _ (by simp)]
  change _ ++ encodeUnaryFrameWithFixedDelimiters
      (affineUnaryTripleMap
        (transitionAffineOrFieldForms
          (transitionAffineOneHotPredicateCanonicalFrames start source f))
        seed)
      (transitionAffineOrDelimiters
        (transitionAffineOneHotPredicateCanonicalFrames start source f)) = _
  rw [transitionAffineOr_fixed_encoding]
  simp [encodeAffineStmtControllerPhase, affineStmtPhaseTagCode,
    affineStmtPhasePayload, transitionZeroForm,
    affineUnaryTripleFormValue, encodeUnaryFrameWithFixedDelimiters]

/-- One transition seed's complete predicate phase agrees with the canonical
semantic predicate phase. -/
theorem transitionAffineOneHotPredicatePhaseRow_eq_encoding {n : Nat}
    (start : AffineUnaryTripleForm)
    (source : Fin n → AffineUnaryTripleForm) (f : Fin n → Bool)
    (seed : TransitionRowSeed) :
    transitionAffineDelimitedMapRow
        (transitionAffineOneHotPredicatePhaseFieldForms start source f)
        (transitionAffineOneHotPredicatePhaseDelimiters start source f) seed =
      encodeAffineStmtControllerPhase
        (.oneHotPredicate
          (affineOneHotPredicateCanonicalFrames
            (affineUnaryTripleFormValue start
              (transitionTailAffineSeed seed))
            (fun i => affineUnaryTripleFormValue (source i)
              (transitionTailAffineSeed seed)) f)) := by
  unfold transitionAffineDelimitedMapRow
  rw [transitionAffineOneHotPredicatePhase_fixed_encoding]
  rw [transitionAffineOneHotPredicateCanonicalFrames_eval]

/-- Raw-input target containing one complete tagged predicate phase per
transition row. -/
noncomputable def verifierTransitionAffineOneHotPredicatePhase
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    {n : Nat} (start : AffineUnaryTripleForm)
    (source : Fin n → AffineUnaryTripleForm) (f : Fin n → Bool)
    (input : List Γ) : List UnaryFrameSym :=
  verifierTransitionAffineDelimitedMapFrames W
    (transitionAffineOneHotPredicatePhaseFieldForms start source f)
    (transitionAffineOneHotPredicatePhaseDelimiters start source f)
    (transitionAffineOneHotPredicatePhaseDelimiters_nonempty start source f)
    input

/-- Exact row-major semantics of the complete predicate-phase compiler. -/
theorem verifierTransitionAffineOneHotPredicatePhase_eq_rows
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    {n : Nat} (start : AffineUnaryTripleForm)
    (source : Fin n → AffineUnaryTripleForm) (f : Fin n → Bool)
    (input : List Γ) :
    verifierTransitionAffineOneHotPredicatePhase W start source f input =
      (verifierTransitionRowSeeds W input).flatMap fun seed =>
        encodeAffineStmtControllerPhase
          (.oneHotPredicate
            (affineOneHotPredicateCanonicalFrames
              (affineUnaryTripleFormValue start
                (transitionTailAffineSeed seed))
              (fun i => affineUnaryTripleFormValue (source i)
                (transitionTailAffineSeed seed)) f)) := by
  unfold verifierTransitionAffineOneHotPredicatePhase
  rw [verifierTransitionAffineDelimitedMapFrames_eq_rows W
    (transitionAffineOneHotPredicatePhaseFieldForms start source f)
    (transitionAffineOneHotPredicatePhaseDelimiters start source f)
    (transitionAffineOneHotPredicatePhaseDelimiters_nonempty start source f)
    (transitionAffineOneHotPredicatePhase_lengths start source f)]
  apply List.flatMap_congr
  intro seed hseed
  exact transitionAffineOneHotPredicatePhaseRow_eq_encoding start source f seed

/-- One fixed polynomial-time TM2 emits the complete tagged predicate phase
directly from the original verifier input. -/
noncomputable def
    verifierTransitionAffineOneHotPredicatePhase_computableInPolyTime
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    {n : Nat} (start : AffineUnaryTripleForm)
    (source : Fin n → AffineUnaryTripleForm) (f : Fin n → Bool) :
    _root_.Turing.TM2ComputableInPolyTime id id
      (verifierTransitionAffineOneHotPredicatePhase W start source f) :=
  verifierTransitionAffineDelimitedMapFrames_computableInPolyTime W
    (transitionAffineOneHotPredicatePhaseFieldForms start source f)
    (transitionAffineOneHotPredicatePhaseDelimiters start source f)
    (transitionAffineOneHotPredicatePhaseDelimiters_nonempty start source f)

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