Theorem H.5 — clause-probe B&B threshold ERM is NP-complete
OpenAggCG.Supplement.theorem_H_5algorithm-configurationcomputational-complexitymachine-learningoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1
For the fixed clause-reading branch-and-bound policy, deciding whether some makes
is NP-complete for clauses with at most three literals, and remains NP-complete for clauses with at most two literals. Evaluation at a specified rational parameter is polynomial-time. The reduction produces MILPs with variables and constraints and polynomially bounded coefficients.
Differences from the source:
- encoding: the source describes the threshold inputs, policy, and polynomial bounds in prose → Lean uses explicit formula, parameter, threshold, and MILP encodings, with one uniform constant for the size and coefficient bounds; reason: these codes are the stated restricted clause-probe family and make the complexity claims well-defined
Preamble
import Mathlib import Definitions.Def_CookLevin_Complexity import Definitions.Def_KSat_Languages import Definitions.Def_AggCG_Supplement_clauseProbeMILP import Definitions.Def_AggCG_Supplement_CGInst
Formal statement
namespace AggCG.Supplement
/-- **Theorem H.5** (NP-complete ERM threshold decision; Sharma, *Computational Complexity of Data-Driven
Configuration for Integer Programming, Clustering, and Learning Algorithms*, STOC 2027 submission
(manuscript sha256 f7ea0248…), p.47, PDF p.48), for the fixed B&B policy family of §H.2 on the
clause-probe MILPs (8)–(12) with block sizes (15):
(1) deciding whether some `θ ∈ [0, 1]` has `Σ_{a=1}^m TreeSize_θ(Q_{C_a}) ≤ K` is NP-complete on the
restricted family with at most three literals per clause;
(2) it remains NP-complete with at most two literals per clause;
(3) each training-instance evaluation at a specified rational parameter takes polynomial time;
(4) the hardness reduction (from 3-SAT on `T` variables and `m` clauses) outputs MILPs with
`O(T + log(mT))` variables and constraints and polynomially bounded coefficients, with one constant.
**Formalization Note** Variables of a clause are `0, …, T − 1`; `T` in (4) is the formula's variable count
`numVars`. Tree sizes are those of `probeTreeSize` (generated nodes, root and trap roots included). -/
theorem theorem_H_5 :
CookLevin.NPComplete (ProbeTreeLang 3) ∧
CookLevin.NPComplete (ProbeTreeLang 2) ∧
(∃ g : List Bool → List Bool, CookLevin.IsPolyTimeComputable g ∧
∀ (T kstar : ℕ) (C : CookLevin.Clause) (q : ℚ), Odd kstar → ProbeClause 3 T C → 0 ≤ q → q ≤ 1 →
g (encodeProbeSet' T kstar [C] ++ QAlgorithms.LocalHamiltonian.encRat q) =
QAlgorithms.LocalHamiltonian.encBin (probeTreeSize T (clauseSizes T C kstar) q)) ∧
(∃ C₀ : ℕ, ∃ f : List Bool → List Bool, CookLevin.IsPolyTimeComputable f ∧
(∀ x, KSat.KSAT 3 x ↔ ProbeTreeLang 3 (f x)) ∧
∀ φ : CookLevin.Formula, (∀ C ∈ φ, ProbeClause 3 (numVars φ) C) → ∃ kstar K : ℕ,
f (CookLevin.encodeFormula φ) = encodeProbeSet (numVars φ) kstar φ K ∧ Odd kstar ∧
∀ C ∈ φ,
Fintype.card (HVar (numVars φ) (clauseSizes (numVars φ) C kstar)) ≤
C₀ * (numVars φ + Nat.log 2 (φ.length * numVars φ + 2) + 1) ∧
(clauseProbeMILP (numVars φ) (clauseSizes (numVars φ) C kstar)).rows.length ≤
C₀ * (numVars φ + Nat.log 2 (φ.length * numVars φ + 2) + 1) ∧
∀ r ∈ (clauseProbeMILP (numVars φ) (clauseSizes (numVars φ) C kstar)).rows,
(∀ v, |r.1 v| ≤ C₀ * (numVars φ + φ.length + 1)) ∧ |r.2.2| ≤ C₀ * (numVars φ + φ.length + 1)) := by sorry
end AggCG.Supplement
Source
Sharma, STOC 2027 submission (manuscript sha256 f7ea0248…), Theorem H.5, p.47, PDF p.48