Near-Inverse-Linear Barriers for Explicit Affine Witness Isolation
Abstract
We study randomized nonuniform polynomial-size transformations that output explicit binary affine filters for circuit inputs whose nonempty satisfying sets are affine. The filter may depend on the entire input description; no affine basis is supplied. For every fixed $\delta<1$, a worst-case singleton success guarantee $\Omega(n^{-\delta})$, where $n$ is the witness arity, implies $NP\subseteq P/poly$. More generally, any success guarantee $\omega(\log n/n)$ yields satisfiability circuits of size $(s+2)^{O(1)}2^{o(v)}$ for length-$s$ descriptions with at most $v$ witness variables, hence subexponential in $v$ when $s=v^{O(1)}$. Conversely, SAT search-to-decision gives deterministic perfect isolation, making polynomial-resource fixed-exponent strong affine isolation equivalent to $NP\subseteq P/poly$. For explicit unions of at most $n^\beta$ affine components, success $\Omega(n^{-\delta})$ implies the same collapse whenever $\beta,\delta\ge0$ and $\beta+\delta<1$. The inverse-linear endpoint is not claimed.