Constant probability witness isolation implies NP problems have small circuits
Constant-Probability Witness Isolation Implies $\mathrm{NP}\subseteq\mathrm{P/poly}$
Computational Complexity
Summary
The paper studies a way to pick out a solution to a complex problem with a guaranteed small chance of success. The authors show that if a method exists that isolates solutions with any fixed positive chance, then it would mean that very hard problems (NP) could be solved using small, fixed-size advice circuits (P/poly). They prove this by combining many problems into one circuit and analyzing how solutions overlap in special regions, revealing limits on success probabilities. Their result bridges a gap between known lower and higher probabilities but leaves some parts still open.
What this means in practice
- •For complexity theorists: Understand limits of randomized methods to isolate solutions in NP problems and their implications for circuit complexity.
- •For cryptographers: Recognize that certain probabilistic pruning procedures imply a collapse of NP and so no cryptographic assumptions are needed for their analysis.
A theory result. No direct application yet.
Authors
Sebastian Ben Daniel
Abstract
Valiant and Vazirani isolate a satisfying assignment of a circuit with probability $Ω(1/n)$. Dell, Kabanets, van Melkebeek, and Watanabe showed that success above $2/3$ implies $\mathrm{NP}\subseteq\mathrm{P/poly}$ and asked about the range in between. We show that every positive constant already implies the collapse: if a randomized nonuniform polynomial-size pruning procedure succeeds with probability $ε$ on affine circuit inputs with at most $2^{\lfloor 2/ε\rfloor}$ satisfying assignments, then $\mathrm{NP}\subseteq\mathrm{P/poly}$. Success $10/\log L$ on affine inputs with at most $L^{1/3}$ satisfying assignments suffices, where $L$ is the description length, and on inputs with one or two satisfying assignments the threshold $2/3$ drops to $3/5$. No cryptographic assumption is used, and the procedure may read the entire circuit. The proof compiles a pool of circuits into one circuit whose satisfying assignments are indexed by tags in $\mathbb{F}_2^d$. Each member is assigned an affine region of tag space, and if one member is unsatisfiable, the satisfying set shrinks to that member's region. Because regions may overlap and have different dimensions, the collapse reduces to a combinatorial bound: no set of tags meets more than a $2/d$ fraction of an equally weighted family of affine subspaces of all dimensions below $d$ in exactly one point. This regional counting cannot go below order $1/\log L$. The range between $Θ(1/n)$, achieved by affine hashing, and $O(1/\log n)$ remains open.