Theorem 3.7 — exact-zero deletion is NP-hard
OpenSampleRemoval.Supplement.theorem_3_7least-squaresoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1robustness-auditsample-removal
Consider the following decision problem. The input is a finite list of observations with and integer , together with an integer deletion budget . The answer is yes when deleting at most observations leaves a nonsingular intercept-plus-binary-regressor design whose OLS slope is exactly zero.
Theorem 3.7 states that this language is NP-hard under polynomial-time many-one reductions. The result is weak NP-hardness, consistently with the paper's pseudo-polynomial dynamic program for small integer responses.
Differences from the source:
- encoding: an unspecified finite input encoding and the standard phrase NP-hard → a canonical self-delimiting Boolean encoding and Cook–Levin polynomial-time many-one NP-hardness; reason: a complexity-theoretic Lean statement requires a concrete language and machine model, and this standard encoding represents exactly the source instances
Preamble
import Mathlib import Definitions.Def_CookLevin_Complexity import Definitions.Def_SampleRemoval_Supplement_exactZeroDeletionLang set_option autoImplicit false
Formal statement
namespace SampleRemoval.Supplement /-- **Theorem 3.7 (Equality targets are hard).** The exact-zero integral deletion decision problem is NP-hard even for an intercept and one binary regressor with integer responses (Xu, Gao, Hu, *Rounding, Ranges, and Exact Sample-Removal Audits for Least Squares*, STOC 2027 submission, manuscript sha256 `dcd33ace…`, Theorem 3.7, p.6 (PDF p.8)). **Formalization Note** NP-hardness is polynomial-time many-one hardness in the published Cook–Levin multi-tape Turing-machine model. `exactZeroDeletionLang` uses a canonical binary encoding of the list `(xᵢ,yᵢ)` and budget `k`; membership requires deletion of at most `k` observations, a positive-definite retained intercept-plus-regressor design, and exactly zero OLS slope. This is the paper's weak NP-hardness claim; no strong-hardness claim is made. -/ theorem theorem_3_7 : CookLevin.NPHard exactZeroDeletionLang := by sorry end SampleRemoval.Supplement
Source
Xu, Gao, Hu, Rounding, Ranges, and Exact Sample-Removal Audits for Least Squares, STOC 2027 submission (manuscript sha256 dcd33acebc1ccdc626c7ee41bfabc29795abe2e1cd9267d8cbd66d98f81c4b26), Theorem 3.7, p.6 (PDF p.8)