Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.GeneralClique.OccurrenceReduction.Machine.CompatibilityEdgesSemantics

Definition
PricingWithTips3DM_b29b44a24fc19d7b58cd2a69

by qmaai2907271020 · Oct 23, 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_d45ede390e2ec9beab47cf24
import Mathlib.Tactic
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Occurrence compatibility edges: canonical semantics

This file identifies the edge order accumulated by the compatibility
controller with the textbook `normalizedPairs` enumeration used by the
general CLIQUE instance.
-/

noncomputable section

namespace CLRS
namespace Chapter34
namespace Turing
namespace TMClique

open PolyBuilder

private def occurrenceCliqueEdgesFor
    (occurrences : List IndexedOccurrence) : List (Nat × Nat) :=
  (normalizedPairs occurrences.length).filter fun edge =>
    match occurrences[edge.1]?, occurrences[edge.2]? with
    | some left, some right => decide (left.Compatible right)
    | _, _ => false

private def encodeOccurrenceCliqueEdgesFor
    (occurrences : List IndexedOccurrence) : List CliqueSym :=
  (occurrenceCliqueEdgesFor occurrences).flatMap encodeCliqueEdge

/-- The controller's executable comparison bit is exactly the semantic
compatibility predicate on the two indexed occurrences. -/
theorem indexedOccurrencesCompatibleCode_eq_decide
    (current prior : IndexedOccurrence × Nat) :
    indexedOccurrencesCompatibleCode current prior =
      decide (prior.1.Compatible current.1) := by
  rcases current with ⟨⟨cc, cp, cl⟩, cv⟩
  rcases prior with ⟨⟨pc, pp, pl⟩, pv⟩
  cases cl <;> cases pl <;>
    simp [indexedOccurrencesCompatibleCode, occurrenceRowsCompatibleCode,
      IndexedOccurrence.Compatible, occurrencePolarityFlag,
      occurrenceVariableCode, complement]

private theorem zipIdx_map_snd (occurrences : List IndexedOccurrence) :
    occurrences.zipIdx.map Prod.snd = List.range occurrences.length := by
  rw [List.zipIdx_eq_zip_range', List.range_eq_range']
  apply List.map_snd_zip
  rw [List.length_range']

private theorem oldFilter_eq (occurrences : List IndexedOccurrence)
    (right : IndexedOccurrence) :
    List.filter
      (fun edge =>
        match (occurrences ++ [right])[edge.1]?,
            (occurrences ++ [right])[edge.2]? with
        | some left, some right => decide (left.Compatible right)
        | _, _ => false)
      (normalizedPairs occurrences.length) =
    List.filter
      (fun edge =>
        match occurrences[edge.1]?, occurrences[edge.2]? with
        | some left, some right => decide (left.Compatible right)
        | _, _ => false)
      (normalizedPairs occurrences.length) := by
  apply List.filter_congr
  intro edge hedge
  have hbounds := normalizedPairs_mem_iff.mp hedge
  have hleft : edge.1 < occurrences.length :=
    lt_trans hbounds.1 hbounds.2
  simp [List.getElem?_append, hleft, hbounds.2]

private theorem flatMap_filter_bool {α β : Type} (p : α → Bool)
    (f : α → List β) (xs : List α) :
    (xs.filter p).flatMap f =
      xs.flatMap fun x => if p x then f x else [] := by
  induction xs with
  | nil => rfl
  | cons x xs ih =>
      cases h : p x <;> simp [h, ih]

private theorem newFilterEncoding_eq
    (occurrences : List IndexedOccurrence) (right : IndexedOccurrence) :
    List.flatMap encodeCliqueEdge
      (List.filter
        (fun edge =>
          match (occurrences ++ [right])[edge.1]?,
              (occurrences ++ [right])[edge.2]? with
          | some left, some right => decide (left.Compatible right)
          | _, _ => false)
        ((List.range occurrences.length).map fun u =>
          (u, occurrences.length))) =
      encodeCompatibleOccurrenceEdges (right, occurrences.length)
        occurrences.zipIdx := by
  have hindices :
      (List.range occurrences.length).map
          (fun u => (u, occurrences.length)) =
        occurrences.zipIdx.map fun prior =>
          (prior.2, occurrences.length) := by
    calc
      _ = (occurrences.zipIdx.map Prod.snd).map
          (fun u => (u, occurrences.length)) := by
            rw [zipIdx_map_snd]
      _ = _ := by
        simp only [List.map_map]
        rfl
  rw [hindices, List.filter_map, List.flatMap_map]
  have hpredicate : ∀ prior ∈ occurrences.zipIdx,
      (match (occurrences ++ [right])[prior.2]?,
          (occurrences ++ [right])[occurrences.length]? with
        | some left, some right => decide (left.Compatible right)
        | _, _ => false) =
      decide (prior.1.Compatible right) := by
    intro prior hprior
    have hfields := List.mem_zipIdx hprior
    have hbound : prior.2 < occurrences.length := by omega
    have hvalue : prior.1 = occurrences[prior.2] := by
      simpa using hfields.2.2
    simp [List.getElem?_append, hbound, hvalue]
  rw [List.filter_congr (fun prior hprior => by
    simpa only [Function.comp_apply] using hpredicate prior hprior)]
  rw [flatMap_filter_bool]
  unfold encodeCompatibleOccurrenceEdges
  apply List.flatMap_congr
  intro prior hprior
  simp [encodeCompatibleOccurrenceEdge,
    indexedOccurrencesCompatibleCode_eq_decide]

private theorem occurrenceCliqueEdgesFor_append_singleton
    (occurrences : List IndexedOccurrence) (right : IndexedOccurrence) :
    encodeOccurrenceCliqueEdgesFor (occurrences ++ [right]) =
      encodeOccurrenceCliqueEdgesFor occurrences ++
        encodeCompatibleOccurrenceEdges (right, occurrences.length)
          occurrences.zipIdx := by
  unfold encodeOccurrenceCliqueEdgesFor occurrenceCliqueEdgesFor
  simp only [List.length_append, List.length_singleton,
    normalizedPairs, List.filter_append, List.flatMap_append]
  rw [oldFilter_eq, newFilterEncoding_eq]

private theorem encodeCompatibleOccurrenceIterations_reverse_zipIdx
    (occurrences : List IndexedOccurrence) :
    encodeCompatibleOccurrenceIterations occurrences.zipIdx.reverse =
      encodeOccurrenceCliqueEdgesFor occurrences := by
  induction occurrences using List.reverseRecOn with
  | nil =>
      simp [encodeCompatibleOccurrenceIterations,
        encodeOccurrenceCliqueEdgesFor, occurrenceCliqueEdgesFor,
        normalizedPairs]
  | append_singleton occurrences right ih =>
      rw [List.zipIdx_append]
      simp only [List.zipIdx_singleton, Nat.zero_add, List.reverse_append,
        List.reverse_singleton]
      change encodeCompatibleOccurrenceIterations
          ((right, occurrences.length) :: occurrences.zipIdx.reverse) = _
      rw [encodeCompatibleOccurrenceIterations, List.reverse_reverse, ih,
        occurrenceCliqueEdgesFor_append_singleton]

/-- Exhausting the loaded canonical occurrence rows emits precisely the
serialized edge suffix of the textbook occurrence graph, in its canonical
normalized-pair order. -/
theorem encodeCompatibleOccurrenceIterations_canonical (formula : CNF) :
    encodeCompatibleOccurrenceIterations
        (indexedOccurrences formula).zipIdx.reverse =
      encodeOccurrenceCliqueEdges formula := by
  rw [encodeCompatibleOccurrenceIterations_reverse_zipIdx]
  rfl

end TMClique
end Turing
end Chapter34
end CLRS
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