Theorem H.6 — constant-additive B&B ERM inapproximability
OpenAggCG.Supplement.theorem_H_6algorithm-configurationcomputational-complexitymachine-learningoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1
There is a universal such that a polynomial-time algorithm returning a parameter within additive of the optimal average normalized B&B tree size on the three-literal probe family would imply . The normalization is
and every fixed rational-parameter B&B run in the reduction is polynomial-time computable.
Differences from the source:
- encoding: returning a parameter within additive of the optimum → returning a rational whose loss is strictly below every comparison parameter's loss plus ; reason: this is the paper's algorithmic output model and is equivalent to the stated additive guarantee after decreasing the universal constant if necessary
Preamble
import Mathlib import Definitions.Def_CookLevin_Complexity import Definitions.Def_AggCG_PEqNP import Definitions.Def_AggCG_Supplement_clauseProbeMILP
Formal statement
namespace AggCG.Supplement
/-- **Theorem H.6** (Constant-additive inapproximability; Sharma, *Computational Complexity of Data-Driven
Configuration for Integer Programming, Clustering, and Learning Algorithms*, STOC 2027 submission
(manuscript sha256 f7ea0248…), p.48, PDF p.49). There is a universal constant `δ > 0` such that a
polynomial-time algorithm that always returns a parameter whose average normalized B&B tree size
`(1/m) Σ_a TreeSize_θ(Q_{C_a})/M`, `M = H + 2T + 3 + 38T`, `H = h(k∗)`, is within additive `δ` of the
optimal average, on the three-literal clause-probe family, gives `P = NP`; and every fixed-parameter B&B
run of the family is computable in polynomial time.
**Formalization Note** The normalization `M = B + H` with `B = 2T + 3 + 38T` is the one of the proof
(p.48) and of Theorem H.7. The algorithm reads the training set and returns the code of a rational
`q ∈ [0, 1]`; "within additive `δ`" is strict against every `θ ∈ [0, 1]`, as in the published
`AggCG.IsAdditiveApprox`. "Unless P = NP" is the published `AggCG.PEqNP`. -/
theorem theorem_H_6 :
(∃ δ : ℝ, 0 < δ ∧ ∀ A : List Bool → List Bool, CookLevin.IsPolyTimeComputable A →
(∀ (T kstar : ℕ) (Φ : CookLevin.Formula), Odd kstar → (∀ C ∈ Φ, ProbeClause 3 T C) →
∃ q : ℚ, A (encodeProbeSet' T kstar Φ) = QAlgorithms.LocalHamiltonian.encRat q ∧ 0 ≤ q ∧ q ≤ 1 ∧
∀ θ ∈ Set.Icc (0 : ℝ) 1, avgNormTree T kstar Φ q < avgNormTree T kstar Φ θ + δ) →
AggCG.PEqNP) ∧
(∃ 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)) := by sorry
end AggCG.Supplement
Source
Sharma, STOC 2027 submission (manuscript sha256 f7ea0248…), Theorem H.6, p.48, PDF p.49