Randomized affine filters link satisfiability to complexity class collapse
Near-Inverse-Linear Barriers for Explicit Affine Witness Isolation
Computational Complexity
Summary
The paper explores special filters that can recognize certain structured solutions in logical problems. These filters work when the solutions form neat, affine shapes, but creating them reliably would imply a major breakthrough in computer science theory. Specifically, if such filters succeed often enough, it means a hard complexity problem (NP) could be solved easily with small advice information, collapsing important complexity classes. The authors establish tight connections between how well these filters perform and fundamental limits in computational complexity.
What this means in practice
- •For circuit designers: Determine theoretical limits when using affine filters for isolating satisfying inputs in circuit analysis and optimization.
- •For cryptographic engineers: Guide secure system designs by understanding when certain affine witness isolations imply unlikely complexity class collapses.
A theory result. No direct application yet.
Authors
Sebastian Ben Daniel
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 $δ<1$, a worst-case singleton success guarantee $Ω(n^{-δ})$, where $n$ is the witness arity, implies $NP\subseteq P/poly$. More generally, any success guarantee $ω(\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^β$ affine components, success $Ω(n^{-δ})$ implies the same collapse whenever $β,δ\ge0$ and $β+δ<1$. The inverse-linear endpoint is not claimed.