Less Is Harder Than More: Proving Unnecessary Complexity
Tristan Simas
原文摘要
When can a sensor, feature, or API field be removed without changing a fixed system's decisions? We require the remaining inputs to recover its complete optimal-action set, including ties, at every admitted state. Admitting every input combination guarantees one smallest preserving set. Yet checking one deletion is coNP-complete when circuits give utilities on Boolean products, even with two actions and at most two optimal-action sets. Missing combinations permit alternative preserving sets, so an auditor must choose inputs within budget and check the chosen set. Requiring every declared reading to have a positive-probability state adds a support check. We classify choosing and checking exactly for circuit-defined Boolean models, with and without the support requirement. A unique winner after averaging hidden states can still change the original decisions. Certifying such winners requires weighted score comparisons: finding inputs within budget is $\mathsf{NP}^{(\mathsf{NP}^{\mathsf{PP}})}$-complete even with two actions and independent uniform inputs. Explicit tables admit logarithmic approximation of the minimum preserving input count; succinct Boolean products admit no polynomial-time $o(Λ/\logΛ)$ approximation in total encoded length $Λ$, unless $\mathsf P=\mathsf{NP}$. Supplied decompositions and symmetry proofs can make audits polynomial-time; discovery and validation are additional work. For a frozen digit classifier, eleven blocks suffice on held-out rows but fifteen are needed on the full product; four conflicting pairs expose the gap. Building the required response from retained inputs establishes sufficiency, not minimality. Preserve the structure that makes the dependence checkable.
cs.CC