Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_025fdc9044b7210f13e0288b

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

/-!
# General CLIQUE verifier: complete canonical edge lookup
-/

noncomputable section

open StateTransition

namespace CLRS.Chapter34.Turing.GeneralCliqueVerifier.EdgeLookup

open PolyBuilder

/-- Exact execution cost of a complete canonical edge-membership query. -/
def edgeLookupSteps (query : Nat × Nat) (I : CliqueInstance) : Nat :=
  headerSteps query I + edgesSteps query I.edges

/-- Exact independent-semantics run from the raw query-instance pair to edge
membership. -/
def edgeLookup_run (query : Nat × Nat) (I : CliqueInstance) :
    EvalsToInTime (step program)
      (initialCfg program
        (pairEncoding (encodeCliqueEdge query) (encodeCliqueInstance I)))
      (some (haltCfg program [decide (query ∈ I.edges)]))
      (edgeLookupSteps query I) := by
  have first := header_run query I
  have first' : EvalsToInTime (step program)
      (initialCfg program
        (pairEncoding (encodeCliqueEdge query) (encodeCliqueInstance I)))
      (some (cfg .edges (some (some .fieldSep)) none false
        ((I.edges.flatMap encodeCliqueEdge).map some) []
        (List.replicate query.1 ()) (List.replicate query.2 ()) []))
      (headerSteps query I) := by
    simpa [initialCfg, cfg, program] using first
  have second := edges_run query I.edges (some (some .fieldSep)) none false
  let full := EvalsToInTime.trans (step program)
    (headerSteps query I) (edgesSteps query I.edges) _ _ _ first' second
  simpa [edgeLookupSteps, Nat.add_assoc, Nat.add_comm, Nat.add_left_comm]
    using full

/-- Below the diagonal, the concrete lookup machine computes the graph's
typed adjacency predicate. -/
def edgeLookup_adjacency_run (I : CliqueInstance) {u v : Nat} (huv : u < v) :
    EvalsToInTime (step program)
      (initialCfg program
        (pairEncoding (encodeCliqueEdge (u, v)) (encodeCliqueInstance I)))
      (some (haltCfg program [adjacencyBool I u v]))
      (edgeLookupSteps (u, v) I) := by
  simpa [adjacencyBool, huv] using edgeLookup_run (u, v) I

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