Theorem K.1 — box-robust scalar batch-CG hardness
OpenAggCG.Supplement.theorem_K_1algorithm-configurationcomputational-complexitymachine-learningoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1
A polynomial-time reduction maps 3-SAT to one-variable IPs with at most three separately rounded rows. Under every permitted additive perturbation of every numerical occurrence,
Pointwise, , it equals exactly when , and a positive gap loss is at least . Exact ERM is NP-hard; finite-factor remaining-gap approximation and one fixed additive approximation for both average remaining gap and average excess tree size imply . Coefficients and canonical witnesses use bits, rational root evaluation is polynomial-time, and every perturbed unary family has .
Differences from the source:
- encoding: and polynomial-time rational evaluation → an explicit attaining witness and self-delimiting rational input/output codes; reason: the minimum in the source is attained by its canonical witnesses, and the codes make the same computational claim precise
Preamble
import Mathlib import Definitions.Def_CookLevin_Complexity import Definitions.Def_KSat_Languages import Definitions.Def_BartlettNN_Margin_FatShattering import Definitions.Def_AggCG_PEqNP import Definitions.Def_AggCG_Supplement_CGInst
Formal statement
namespace AggCG.Supplement
/-- **Theorem K.1** (Box-robust scalar CG hardness; Sharma, *Computational Complexity of Data-Driven
Configuration for Integer Programming, Clustering, and Learning Algorithms*, STOC 2027 submission
(manuscript sha256 f7ea0248…), p.59, PDF p.60), for the scalar batch-CG policy of §K (p.58):
(1) a polynomial-time reduction `f` from 3-SAT to collections of one-variable, at-most-three-row IPs;
on a formula whose clauses have one to three literals on distinct variables it outputs the unperturbed
clause instances (one row (21) per literal, `q_i = 1000^i`, objective `min x`);
(2) for every such formula and every permitted perturbation of every numerical occurrence,
`min_{θ∈[0,1]} Σ_C L_C(θ) = 0` iff the formula is satisfiable;
(3) for every clause instance, permitted perturbation and `θ ∈ [0, 1]`: `TS_C(θ) ∈ {1, 3}`,
`TS_C(θ) = 1 ⟺ L_C(θ) = 0`, and `L_C(θ) > 0 ⟹ L_C(θ) ≥ 4/5`;
(4) exact ERM is NP-hard; a polynomial-time finite-factor approximation of the nonnegative remaining-gap
loss gives `P = NP`; for one fixed `c > 0`, a polynomial-time additive-`c` approximation of the average
normalized remaining gap, or of the average excess tree size, gives `P = NP`;
(5) every coefficient entry of the encoding and every canonical witness `θ_σ` of (23) has `O(T)` bits;
(6) each fixed-parameter root evaluation `L_C(q)` at a rational `q` is polynomial-time computable on rational
inputs;
(7) for every `T` and every permitted perturbation of the `T` unary instances `(x_i)`, the normalized
remaining-gap class `1/2`-fat-shatters them (non-strict convention).
**Formalization Note** "Unless P = NP" is the published `AggCG.PEqNP`. The NP-hardness and approximation
clauses are stated on the unperturbed rational family (`IsCanonColl`); the perturbation clauses (2), (3),
(7) are pointwise over real perturbations. `min_θ … = 0` is read as attained (some `θ` gives `0`). -/
theorem theorem_K_1 :
(∃ f : List Bool → List Bool, CookLevin.IsPolyTimeComputable f ∧
(∀ x, KSat.KSAT 3 x ↔ CGZeroLang (f x)) ∧
∀ φ : CookLevin.Formula, (∀ C ∈ φ, WellFormedClause C) →
f (CookLevin.encodeFormula φ) = encodeCGColl (φ.map canonInstQ)) ∧
(∀ φ : CookLevin.Formula, (∀ C ∈ φ, WellFormedClause C) →
∀ P : List CGInst, List.Forall₂ IsPermittedPerturbation (φ.map canonInst) P →
((∃ θ ∈ Set.Icc (0 : ℝ) 1, (P.map fun I => I.gapLoss θ).sum = 0) ↔
CookLevin.Satisfiable φ)) ∧
(∀ C : CookLevin.Clause, WellFormedClause C → ∀ I : CGInst,
IsPermittedPerturbation (canonInst C) I → ∀ θ ∈ Set.Icc (0 : ℝ) 1,
(I.treeSize θ = 1 ∨ I.treeSize θ = 3) ∧ (I.treeSize θ = 1 ↔ I.gapLoss θ = 0) ∧
(0 < I.gapLoss θ → 4 / 5 ≤ I.gapLoss θ)) ∧
CookLevin.NPHard CGERMLang ∧
(∀ A : List Bool → List Bool, CookLevin.IsPolyTimeComputable A →
IsFactorApproxCG avgGapLoss A → AggCG.PEqNP) ∧
(∃ c : ℝ, 0 < c ∧
(∀ A : List Bool → List Bool, CookLevin.IsPolyTimeComputable A →
IsAdditiveApproxCG avgGapLoss c A → AggCG.PEqNP) ∧
(∀ A : List Bool → List Bool, CookLevin.IsPolyTimeComputable A →
IsAdditiveApproxCG avgExcessTree c A → AggCG.PEqNP)) ∧
(∃ C : ℕ, (∀ φ : CookLevin.Formula, (∀ C' ∈ φ, WellFormedClause C') →
∀ I ∈ φ.map canonInstQ, ∀ r ∈ I.rows,
(QAlgorithms.LocalHamiltonian.encRat r.1).length ≤ C * (numVars φ + 1) ∧
(QAlgorithms.LocalHamiltonian.encRat r.2.1).length ≤ C * (numVars φ + 1)) ∧
∀ (T : ℕ) (σ : Fin T → Bool), (QAlgorithms.LocalHamiltonian.encRat (cgWitness T σ)).length ≤
C * (T + 1)) ∧
(∃ g : List Bool → List Bool, CookLevin.IsPolyTimeComputable g ∧
∀ (I : CGInstQ) (q : ℚ), I.rows ≠ [] → I.rows.length ≤ 3 →
(∀ r ∈ I.rows, 0 < r.2.1 ∧ r.2.1 < r.1) → 0 < I.w → 0 ≤ q → q ≤ 1 →
∃ v : ℚ, g (I.encode ++ QAlgorithms.LocalHamiltonian.encRat q) =
QAlgorithms.LocalHamiltonian.encRat v ∧ (v : ℝ) = I.toInst.gapLoss q) ∧
(∀ (T : ℕ) (P : Fin T → CGInst),
(∀ i, IsPermittedPerturbation (canonInst [CookLevin.Literal.Pos i.val]) (P i)) →
BartlettNN.Margin.GammaShatters
{g : Fin T → ℝ | ∃ θ ∈ Set.Icc (0 : ℝ) 1, ∀ i, g i = (P i).gapLoss θ} (1 / 2) id) := by sorry
end AggCG.Supplement
Source
Sharma, STOC 2027 submission (manuscript sha256 f7ea0248…), Theorem K.1, p.59, PDF p.60