Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-246 | 11th October 2026 08:03

Constant-Probability Witness Isolation Implies NP in P/poly

RSS-Feed

Abstract:

A pruning procedure maps a Boolean circuit to a circuit on the same variables that accepts only satisfying assignments of the original.
Valiant and Vazirani give a pruning procedure that leaves exactly one satisfying assignment of every satisfiable circuit with probability $\Omega(1/n)$, where $n$ is the number of variables. Dell, Kabanets, van Melkebeek, and Watanabe showed
that success $2/3+1/poly$ would imply $NP\subseteq P/poly$. We show that
every fixed positive success probability implies the same collapse. For $0<\epsilon\le1$ it suffices to have success at least $\epsilon$ on circuits
whose satisfying set is a nonempty affine subspace with at most $2^{\lfloor2/\epsilon\rfloor}$ points. We also derive the collapse from success $10/ log L$ on affine inputs with at most $L^{1/3}$ satisfying
assignments, where $L$ is the description length, and from success $3/5$ plus an inverse-polynomial margin on inputs with one or two satisfying
assignments. The procedure may be nonuniform and may read the entire circuit description. No cryptographic assumption is used.

The proof combines a pool of circuits, each with zero or one satisfying assignment, into one circuit whose satisfying assignments are tagged by points of $F_2^d$. Each pool member owns an affine region of tag space.
If that member is the only unsatisfiable one, the satisfying set shrinks to its region and can be listed using the other members' witnesses, so isolation can be tested on the region without a witness for the candidate.
Regions chosen uniformly within each dimension $0,\ldots,d-1$, with equal weight per dimension, have the property that every set of tags meets at most a $2/d$ fraction of them in exactly one point. A standard domination argument then yields polynomial advice. We also show that this counting
method cannot go below $\Omega(1/log L)$.



ISSN 1433-8092 | Imprint