Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_ce348f99f6d6759132764053

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

/-!
# Batch edge lookup: final cleanup
-/

noncomputable section

open StateTransition

namespace CLRS.Chapter34.Turing.GeneralCliqueVerifier.BatchEdgeLookup

open PolyBuilder

/-- Discard the restored graph and traverse the empty cleanup stacks. -/
def discardGraph_run (answer : Bool) (input : List (Option CliqueSym))
    (output : List Bool)
    (buffer₁ buffer₂ : Option (Option CliqueSym)) (test : Bool) :
    EvalsToInTime (step program)
      (cfg (.discardGraph answer) buffer₁ buffer₂ test input output [] [] [] [] [])
      (some (haltCfg program (answer :: output)))
      (input.length + 8) := by
  induction input generalizing buffer₁ with
  | nil =>
      exact ⟨⟨8, by
        simp [Function.iterate_succ_apply, flip, step, program, cfg, stepOp,
          haltCfg]⟩, le_rfl⟩
  | cons symbol input ih =>
      let after := cfg (.discardGraph answer) (some symbol) buffer₂ test input
        output [] [] [] [] []
      have first : EvalsToInTime (step program)
          (cfg (.discardGraph answer) buffer₁ buffer₂ test (symbol :: input)
            output [] [] [] [] [])
          (some after) 1 :=
        ⟨⟨1, by simp [flip, after, step, program, cfg, stepOp]⟩, le_rfl⟩
      have rest := ih (buffer₁ := some symbol)
      let full := EvalsToInTime.trans (step program)
        1 (input.length + 8) _ after _ first rest
      simpa [Nat.add_assoc, Nat.add_comm, Nat.add_left_comm] using full

/-- Empty query work means the aggregate is final. -/
def final_run (answer : Bool) (input : List (Option CliqueSym))
    (output : List Bool)
    (buffer₁ buffer₂ : Option (Option CliqueSym)) (test : Bool) :
    EvalsToInTime (step program)
      (cfg (.nextQuery answer) buffer₁ buffer₂ test input output [] [] [] [] [])
      (some (haltCfg program (answer :: output)))
      (input.length + 9) := by
  let after := cfg (.discardGraph answer) none buffer₂ test input output [] [] [] [] []
  have first : EvalsToInTime (step program)
      (cfg (.nextQuery answer) buffer₁ buffer₂ test input output [] [] [] [] [])
      (some after) 1 :=
    ⟨⟨1, by simp [flip, after, step, program, cfg, stepOp]⟩, le_rfl⟩
  have rest := discardGraph_run answer input output none buffer₂ test
  let full := EvalsToInTime.trans (step program)
    1 (input.length + 8) _ after _ first rest
  simpa [Nat.add_assoc, Nat.add_comm, Nat.add_left_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