Root-split realizability for power-mean linkage
DefinitionAggCG_Supplement_ZR2algorithm-configurationcomputational-complexitymachine-learningoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1
ZR2 asks whether a symmetric rational metric with a prescribed nontrivial bipartition has some power-mean exponent whose unmodified agglomerative-linkage hierarchy has root split .
The input includes the entire rational distance table and the side ; invalid encodings are rejected.
Definition code
import Mathlib
import Definitions.Def_CookLevin_Satisfiability
import Definitions.Def_QAlgorithms_ClassicalRationalEncoding
import Definitions.Def_AggCG_Supplement_linkageHierarchy
namespace AggCG.Supplement
/-- A rational distance table on `N` points with a proposed side `L` of the root bipartition `L | R`
(Sharma, *Computational Complexity of Data-Driven Configuration for Integer Programming, Clustering, and
Learning Algorithms*, STOC 2027 submission (manuscript sha256 f7ea0248…), §M, p.70, PDF p.71). -/
structure MetricInst where
/-- The number of points. -/
N : ℕ
/-- The distance table. -/
δ : Fin N → Fin N → ℚ
/-- The side `L`; the other side is its complement `R`. -/
L : Finset (Fin N)
namespace MetricInst
/-- A symmetric rational metric (zero diagonal, positive off the diagonal, triangle inequality) with at
least two points, and a proper nonempty side `L`. -/
def Valid (I : MetricInst) : Prop :=
2 ≤ I.N ∧ (∀ i j, I.δ i j = I.δ j i) ∧ (∀ i, I.δ i i = 0) ∧ (∀ i j, i ≠ j → 0 < I.δ i j) ∧
(∀ i j k, I.δ i k ≤ I.δ i j + I.δ j k) ∧ I.L.Nonempty ∧ I.L ≠ Finset.univ
/-- The real distance table. -/
def dist (I : MetricInst) : Fin I.N → Fin I.N → ℝ := fun i j => (I.δ i j : ℝ)
/-- The input code: `N` in unary, the table row by row in self-delimiting binary rationals, then the
membership bits of `L`. -/
def encode (I : MetricInst) : List Bool :=
CookLevin.encodeNat I.N ++
(List.ofFn fun i => (List.ofFn fun j => QAlgorithms.LocalHamiltonian.encRat (I.δ i j)).flatten).flatten ++
List.ofFn fun i => decide (i ∈ I.L)
end MetricInst
/-- **ZR2** (p.70: "ZR2 is the problem of deciding whether some α ∈ ℝ ∪ {±∞} realizes a specified root
bipartition L | R") for a fixed tie rule: the valid inputs whose power-mean linkage run, for some exponent
`α ∈ ℝ ∪ {±∞}`, has root split `{L, R}`. Strings that encode no valid input are rejected.
**Formalization Note** The exponent is an `EReal`, so `α = ±∞` (single and complete linkage) and `α = 0`
(geometric mean) are included. -/
def ZR2 (tie : TieRule) : CookLevin.Language := fun x =>
∃ I : MetricInst, x = I.encode ∧ I.Valid ∧
∃ α : EReal, rootSplit tie I.dist α = {I.L, Finset.univ \ I.L}
end AggCG.Supplement
Source
Sharma, STOC 2027 submission (manuscript sha256 f7ea0248…), §M, p.70, PDF p.71