Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.GeneralClique.VerifierMachine.BatchEdgeLookup.Run

Definition
PricingWithTips3DM_66024f2e1df18ac2bc858dc4

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_2c21a60d99a4b0bdf33b0501
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Batch edge lookup: complete execution

This file closes the operational proof for the fixed batch controller.  The
query stream is loaded once, every query is checked against the same restored
graph, and the conjunction of the answers is emitted.
-/

noncomputable section

open StateTransition

namespace CLRS.Chapter34.Turing.GeneralCliqueVerifier.BatchEdgeLookup

open PolyBuilder

/-- Stack layout used by the repeated-query loop.  Records and the order of
records are both reversed because the work tape is used as a stack. -/
def encodeQueryWork (queries : List (Nat × Nat)) : List (Option CliqueSym) :=
  queries.flatMap fun query => ((encodeCliqueEdge query).map some).reverse

theorem encodeQueryWork_append (left right : List (Nat × Nat)) :
    encodeQueryWork (left ++ right) =
      encodeQueryWork left ++ encodeQueryWork right := by
  simp [encodeQueryWork, List.flatMap_append]

theorem encodeQueryWork_reverse (queries : List (Nat × Nat)) :
    encodeQueryWork queries.reverse =
      ((queries.flatMap encodeCliqueEdge).map some).reverse := by
  induction queries with
  | nil => rfl
  | cons query queries ih =>
      rw [List.reverse_cons, encodeQueryWork_append, ih]
      simp [encodeQueryWork, List.map_append, List.reverse_append]

/-- Exact accumulated cost after all queries have already been loaded. -/
def iterationsSteps : List (Nat × Nat) → CliqueInstance → Nat
  | [], I => (encodeCliqueInstance I).length + 9
  | query :: queries, I =>
      iterationSteps query I + iterationsSteps queries I

/-- Execute every query currently present on the query stack. -/
def iterations_run (aggregate : Bool) (queries : List (Nat × Nat))
    (I : CliqueInstance) (buffer₁ buffer₂ : Option (Option CliqueSym))
    (test : Bool) (output : List Bool) :
    EvalsToInTime (step program)
      (cfg (.nextQuery aggregate) buffer₁ buffer₂ test
        ((encodeCliqueInstance I).map some) output
        (encodeQueryWork queries) [] [] [] [])
      (some (haltCfg program
        ((aggregate && queriesInEdgesBool I queries) ::
          (queryMembershipBits I queries).reverse ++ output)))
      (iterationsSteps queries I) := by
  induction queries generalizing aggregate buffer₁ buffer₂ test output with
  | nil =>
      simpa [encodeQueryWork, iterationsSteps, queriesInEdgesBool,
        queryMembershipBits] using
        final_run aggregate ((encodeCliqueInstance I).map some) output
          buffer₁ buffer₂ test
  | cons query queries ih =>
      have first := iteration_run aggregate query (encodeQueryWork queries) I
        output buffer₁ buffer₂ test
      have rest := ih
        (aggregate := aggregate && decide (query ∈ I.edges))
        (buffer₁ := some (some CliqueSym.edgeMark))
        (buffer₂ := none) (test := false)
        (output := decide (query ∈ I.edges) :: output)
      let full := EvalsToInTime.trans (step program)
        (iterationSteps query I) (iterationsSteps queries I)
        _ _ _ first rest
      simpa [encodeQueryWork, iterationsSteps, queriesInEdgesBool,
        queryMembershipBits,
        Bool.and_assoc, Nat.add_assoc, Nat.add_comm] using full

/-- Exact cost of the full fixed batch edge lookup. -/
def batchSteps (queries : List (Nat × Nat)) (I : CliqueInstance) : Nat :=
  loadSteps queries + iterationsSteps queries.reverse I

/-- The fixed machine emits both the aggregate conjunction and every pointwise
membership answer. -/
def batch_run (queries : List (Nat × Nat)) (I : CliqueInstance) :
    EvalsToInTime (step program)
      (initialCfg program
        (pairEncoding (queries.flatMap encodeCliqueEdge)
          (encodeCliqueInstance I)))
      (some (haltCfg program (batchResultStream I queries)))
      (batchSteps queries I) := by
  have loaded := load_run queries I
  have repeated := iterations_run true queries.reverse I
    (some none) none false []
  rw [encodeQueryWork_reverse] at repeated
  let full := EvalsToInTime.trans (step program)
    (loadSteps queries) (iterationsSteps queries.reverse I)
    _ _ _ loaded repeated
  simpa [batchSteps, batchResultStream, queriesInEdgesBool,
    queryMembershipBits,
    Bool.and_assoc,
    Nat.add_comm] using full

end CLRS.Chapter34.Turing.GeneralCliqueVerifier.BatchEdgeLookup
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