Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_5c7c8fbfa87ce3f62c971fa8

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

/-!
# Executable accepting-row boundary

The total accepting boundary has two literal construction branches.  A
representable target appends complete-row equality; an unrepresentable target
reuses the shared false wire and appends no gates.  The optional equality
controller executes exactly this distinction under one fixed program.
-/

namespace CLRS.Chapter34.Turing.CookLevin

noncomputable section

open StateTransition
open PolyBuilder

def verifierAcceptingOutput
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L) :
    List (W.machine.tm.Γ W.machine.tm.k₁) :=
  List.map W.machine.outputAlphabet.invFun (boolEncoding true)

/-- Static complete halt target used in the representable branch. -/
def verifierAcceptingTargetWires
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (x : List Γ)
    (hfit : AcceptingOutputFits W.machine.tm
      ((verifierHeight W).eval x.length) (verifierAcceptingOutput W)) :=
  let pool := verifierPool W x
  let validity := verifierValidity W x
  let transitions := verifierTransitions W x
  let initial := verifierInitialBoundary W x
  let input := verifierInputBoundary W x
  let output := verifierAcceptingOutput W
  let halphabet := haltList_alphabetBounded_of_fits W.machine.tm
    ((verifierHeight W).eval x.length) output hfit
  let hheight := haltList_height_of_fits W.machine.tm
    ((verifierHeight W).eval x.length) output hfit
  let code := encodeCfg W.machine.tm halphabet hheight
  staticBoundedCfgWires
    (pool.pool.mono (validity.extension.trans
      (transitions.extension.trans (initial.extension.trans input.extension))))
    code

/-- Exact gate list appended by the total accepting boundary. -/
def verifierAcceptingBoundaryGateTrace
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (x : List Γ) : List CircuitGate := by
  classical
  let H := (verifierHeight W).eval x.length
  let rows := verifierRows W x
  let input := verifierInputBoundary W x
  let output := verifierAcceptingOutput W
  by_cases hfit : AcceptingOutputFits W.machine.tm H output
  · exact (CircuitBuilder.eqFinGateTrace input.builder.gates.length
      (fun i => rows.rows (Fin.last ((verifierHorizon W).eval x.length))
        ((cfgSlotEquivFin W.machine.tm H).symm i))
      (fun i => verifierAcceptingTargetWires W x hfit
        ((cfgSlotEquivFin W.machine.tm H).symm i))).gates
  · exact []

/-- The semantic accepting-boundary builder appends exactly the selected
literal branch. -/
theorem verifierAcceptingBoundary_gates_eq
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (x : List Γ) :
    (verifierAcceptingBoundary W x).builder.gates =
      (verifierInputBoundary W x).builder.gates ++
        verifierAcceptingBoundaryGateTrace W x := by
  classical
  let H := (verifierHeight W).eval x.length
  let T := (verifierHorizon W).eval x.length
  let rows := verifierRows W x
  let pool := verifierPool W x
  let validity := verifierValidity W x
  let transitions := verifierTransitions W x
  let initial := verifierInitialBoundary W x
  let input := verifierInputBoundary W x
  let extension := pool.extension.trans (validity.extension.trans
    (transitions.extension.trans (initial.extension.trans input.extension)))
  let row := rows.rows (Fin.last T)
  let hrow := (rows.rowValid (Fin.last T)).mono extension
  let pool' := pool.pool.mono (validity.extension.trans
    (transitions.extension.trans (initial.extension.trans input.extension)))
  let output := verifierAcceptingOutput W
  change (acceptingOutputCircuit W.machine.tm H input.builder pool' row hrow
      output).builder.gates =
    input.builder.gates ++ verifierAcceptingBoundaryGateTrace W x
  by_cases hfit : AcceptingOutputFits W.machine.tm H output
  · have hfit' : AcceptingOutputFits W.machine.tm
        ((verifierHeight W).eval x.length) (verifierAcceptingOutput W) := by
      simpa [H, output] using hfit
    let target := verifierAcceptingTargetWires W x hfit'
    have htarget : target.ValidIn input.builder := by
      exact staticBoundedCfgWires_valid _ _
    rw [show acceptingOutputCircuit W.machine.tm H input.builder pool' row hrow
        output = cfgEqBoundaryCircuit input.builder row target hrow htarget by
      simp only [acceptingOutputCircuit, hfit]
      rfl]
    change (cfgEq input.builder row target hrow htarget).builder.gates = _
    rw [cfgEq_gates_eq]
    have htrace : verifierAcceptingBoundaryGateTrace W x =
        (CircuitBuilder.eqFinGateTrace input.builder.gates.length
          (fun i => row ((cfgSlotEquivFin W.machine.tm H).symm i))
          (fun i => target ((cfgSlotEquivFin W.machine.tm H).symm i))).gates := by
      unfold verifierAcceptingBoundaryGateTrace
      rw [dif_pos hfit']
    rw [htrace]
  · have hfit' : ¬ AcceptingOutputFits W.machine.tm
        ((verifierHeight W).eval x.length) (verifierAcceptingOutput W) := by
      simpa [H, output] using hfit
    rw [show acceptingOutputCircuit W.machine.tm H input.builder pool' row
        hrow output = falseBoundaryCircuit input.builder pool' by
      simp only [acceptingOutputCircuit, hfit]
      rfl]
    change input.builder.gates =
      input.builder.gates ++ verifierAcceptingBoundaryGateTrace W x
    have htrace : verifierAcceptingBoundaryGateTrace W x = [] := by
      unfold verifierAcceptingBoundaryGateTrace
      rw [dif_neg hfit']
    rw [htrace, List.append_nil]

/-- Exact encoded accepting-boundary suffix. -/
def verifierAcceptingBoundaryGateStream
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (x : List Γ) : List CircuitSym :=
  (verifierAcceptingBoundaryGateTrace W x).flatMap encodeCircuitGate

/-- Optional canonical equality frames matching the total constructor's two
branches. -/
def compileVerifierAcceptingBoundaryFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (x : List Γ) : Option (List AffineEqFinPairFrame) := by
  classical
  let H := (verifierHeight W).eval x.length
  let rows := verifierRows W x
  let input := verifierInputBoundary W x
  let output := verifierAcceptingOutput W
  by_cases hfit : AcceptingOutputFits W.machine.tm H output
  · exact some (affineEqFinCanonicalFrames input.builder.gates.length _
      (fun i => rows.rows (Fin.last ((verifierHorizon W).eval x.length))
        ((cfgSlotEquivFin W.machine.tm H).symm i))
      (fun i => verifierAcceptingTargetWires W x hfit
        ((cfgSlotEquivFin W.machine.tm H).symm i)))
  · exact none

theorem compileVerifierAcceptingBoundaryFrames_gateStream_eq
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (x : List Γ) :
    affineOptionalEqFinGateStream
        (compileVerifierAcceptingBoundaryFrames W x) =
      verifierAcceptingBoundaryGateStream W x := by
  classical
  simp only [compileVerifierAcceptingBoundaryFrames,
    verifierAcceptingBoundaryGateStream,
    verifierAcceptingBoundaryGateTrace]
  split <;> rename_i hfit
  · simpa [affineOptionalEqFinGateStream] using
      affineEqFinCanonicalGateStream_eq_trace
        (verifierInputBoundary W x).builder.gates.length
        (fun i =>
          (verifierRows W x).rows
            (Fin.last ((verifierHorizon W).eval x.length))
            ((cfgSlotEquivFin W.machine.tm
              ((verifierHeight W).eval x.length)).symm i))
        (fun i =>
          verifierAcceptingTargetWires W x hfit
            ((cfgSlotEquivFin W.machine.tm
              ((verifierHeight W).eval x.length)).symm i))
  · rfl

/-- One fixed optional-equality controller executes either accepting branch
and emits exactly the semantic suffix. -/
def compileVerifierAcceptingBoundaryFrames_run
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (x : List Γ) (output : List CircuitSym) :
    EvalsToInTime (step affineOptionalEqFinRevProgram)
      (affineOptionalEqFinLoopCfg
        (encodeAffineOptionalEqFin
          (compileVerifierAcceptingBoundaryFrames W x)) output)
      (some (haltCfg affineOptionalEqFinRevProgram
        ((verifierAcceptingBoundaryGateStream W x).reverse ++ output)))
      (affineOptionalEqFinSteps
        (compileVerifierAcceptingBoundaryFrames W x)) := by
  simpa [compileVerifierAcceptingBoundaryFrames_gateStream_eq] using
    affineOptionalEqFin_run
      (compileVerifierAcceptingBoundaryFrames W x) output

end

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