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...
This expanded version of this paper develops the full weak-advantage regime, where saving $2^{-O((log n)^d)}$ gives randomized SAT exponent $d$ and PH exponent $d^k$ at fixed level $k$; the quasipolynomial and exponential hierarchy consequences; binary-comparator advice bounds; and the certificate-length boundary betwe...
The main result extends the optimal nondeterministic advice bound for P-selective sets to every binary membership-comparable language, and a deterministic polynomial-time algorithm for promise Unique-Circuit-SAT gives 2-mc subseteq P/O(n).
It is shown that every positive constant already implies the collapse: if a randomized nonuniform polynomial-size pruning procedure succeeds with probability $\epsilon$ on affine circuit inputs with at most $2^{\lfloor 2/\epsilon\rfloor}$ satisfying assignments, then $\mathrm{NP}\subseteq\mathrm{P/poly}$.
Sebastian Ben Daniel· Electron. Colloquium Comput....· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.