Theorem M.1 — worst-case power-mean root-split hardness
OpenAggCG.Supplement.theorem_M_1algorithm-configurationcomputational-complexitymachine-learningoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every fixed deterministic tie rule, ZR2 is NP-hard under polynomial-time many-one reductions. One reduction from exact three-distinct-literal 3-SAT works uniformly for all tie rules and produces a symmetric rational metric on at most points, with every nonzero distance in and every entry using at most bits, for one universal .
This is NP-hardness only; it does not claim NP membership for arbitrary real exponents.
Differences from the source:
- encoding: points and bits → one positive constant is quantified before the reduction and bounds both quantities for every input; reason: this is the uniform meaning of both asymptotic claims
Preamble
import Mathlib import Definitions.Def_CookLevin_Complexity import Definitions.Def_AggCG_E3 import Definitions.Def_AggCG_Supplement_ZR2
Formal statement
namespace AggCG.Supplement
/-- **Theorem M.1** (= Theorem 3.1; Worst-case root-split linkage hardness; Sharma, *Computational
Complexity of Data-Driven Configuration for Integer Programming, Clustering, and Learning Algorithms*,
STOC 2027 submission (manuscript sha256 f7ea0248…), p.70, PDF p.71; Theorem 3.1, p.4, PDF p.5). ZR2 is
NP-hard under polynomial-time many-one reductions for every fixed deterministic tie rule; one reduction,
from 3-SAT with exactly three distinct variables per clause on `n` variables and `m` clauses, works for
every tie rule at once and produces a symmetric rational metric on at most `C(n + m + 1)²` points whose
nonzero distances lie in `[1, 2]` and whose entries have at most `C(n + log₂(n + m) + 1)` bits, with one
constant `C` for all inputs.
**Formalization Note** The source is the published `AggCG.E3Lang` (exactly three literals on distinct
variables, `T ≥ 3`), the form the paper reduces from (§M.1: "Reduce from 3-SAT with exactly three distinct
variables in each clause"); `n` is the variable count `T` of the input and `m` its clause count. Bits are
lengths of the self-delimiting binary codes. This is NP-hardness only, not NP-completeness. -/
theorem theorem_M_1 :
(∀ tie : TieRule, CookLevin.NPHard (ZR2 tie)) ∧
∃ C : ℝ, 0 < C ∧ ∃ f : List Bool → List Bool, CookLevin.IsPolyTimeComputable f ∧
(∀ tie : TieRule, ∀ x, AggCG.E3Lang x ↔ ZR2 tie (f x)) ∧
∀ (n : ℕ) (φ : CookLevin.Formula), AggCG.E3 n φ → ∃ I : MetricInst,
f (AggCG.encodeE3 n φ) = I.encode ∧ I.Valid ∧
(I.N : ℝ) ≤ C * ((n : ℝ) + φ.length + 1) ^ 2 ∧
(∀ i j, i ≠ j → 1 ≤ I.δ i j ∧ I.δ i j ≤ 2) ∧
∀ i j, ((QAlgorithms.LocalHamiltonian.encRat (I.δ i j)).length : ℝ) ≤
C * ((n : ℝ) + Nat.log 2 (n + φ.length) + 1) := by sorry
end AggCG.Supplement
Source
Sharma, STOC 2027 submission (manuscript sha256 f7ea0248…), Theorem M.1, p.70, PDF p.71; Theorem 3.1, p.4, PDF p.5