Near-Inverse-Linear Barriers for Explicit Affine Witness Isolation
En palabras de los autores
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 , a worst-case singleton success guarantee , where is the witness arity, implies . More generally, any success guarantee yields satisfiability circuits of size for length- descriptions with at most witness variables, hence subexponential in when . Conversely, SAT search-to-decision gives deterministic perfect isolation, making polynomial-resource fixed-exponent strong affine isolation equivalent to . For explicit unions of at most affine components, success implies the same collapse whenever and . The inverse-linear endpoint is not claimed.
Apareció: viernes, 9 de octubre. arXiv. Preprint, todavía sin revisión por pares.