Skip to content

Constant-Probability Witness Isolation Implies NP in P/poly

Sep 2026 · Electron. Colloquium Comput. Complex. · Vol abs/2609.29302 · 1 citation · 24 references
Computer Science

TL;DR

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}$.

Abstract

Valiant and Vazirani isolate a satisfying assignment of a circuit with probability $\Omega(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 $\epsilon$ on affine circuit inputs with at most $2^{\lfloor 2/\epsilon\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 $\Theta(1/n)$, achieved by affine hashing, and $O(1/\log n)$ remains open.

View source

Similar papers

Preprint Sep 2026

Explicit Witnesses at Every Gap of the Depth Filtration of $\beta\mathbb{N}$

Let $\Sigma_{1} = \mathbb{N}^*$ and $\Sigma_{k+1} = \overline{\mathbb{N}^* + \Sigma_{k}}$ be the cumulative depth filtration of $\beta\mathbb{N}$, the analogue for $(\mathbb{N},+)$ of a chain of closed ideals that Protasov and Protasova studied for discrete groups, where strict descent follows from a theorem of Lutsenk...

C. Aza · 0 citations
Preprint Sep 2026

Many Proof Complexity Generators Inside One Demi-Bits Generator

For a propositional proof system $\mathcal{P}$ and a polynomial-time function $G: \{0, 1\}^n \to \{0, 1\}^N$ ($N>10n$), we say that $G$ is a *proof complexity generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the (suitably encoded) statement"$y\not\in\mathrm{Range}(G)$"for every $y \in \{0, 1\}...

Xin Li, Han-Lin Ren, Yan Zhong · 0 citations
Sep 2026

Near-Logarithmic Inapproximability of Parameterized Set Cover

It is shown that for every $\gamma=o(\frac{\log N}{\log\log N})$, $\gamma$-gap $k$-SetCover is W[1]-hard even when $d=O(k^{2}\gamma\log(k\gamma)) and $d^*=O(k\gamma)$.

Bing-Kai Lin, Xin-Rong Zheng · 1 citation
Preprint Sep 2026

Fanout Complexity of Symmetric Boolean Functions in $\mathsf{QAC}^0$

Whether $\mathsf{QAC}^0$ can compute $\mathtt{PARITY}_n$ remains open. Computing $\mathtt{PARITY}_n$ is equivalent to implementing $\mathtt{FANOUT}_n$ under $\mathsf{QAC}^0$ reductions. This raises a more general question: for an arbitrary symmetric Boolean function $f:\{0,1\}^n\to\{0,1\}$, what fanout size is necessar...

Bo-Ya Xu, Lvzhou Li · 0 citations
Preprint Aug 2026

Cohen Forcing with Fra\"iss\'e Classes Beyond $\aleph_1$

Kostana [5] asked for natural conditions on a class $\mathcal{K}$ to ensure that forcing with finite members of $\mathcal{K}$ on an underlying set $X$ is forcing equivalent to Cohen forcing. We show that if $\mathcal{K}_{\triangle}$ is the class of finite triangle-free graphs and $|X|\geq\aleph_2$, then $ \mathbb{C}_X(...

M. Golshani · 0 citations
Sep 2026

BQP ⊆ IP Does Not Relativize

It is shown that any prover-efficient classical interactive protocol for the BQP must rely on non-relativizing techniques, which might serve as a partial explanation for the lack of progress towards doubly-efficient, unconditionally sound classical verification of quantum computation.

Adam Bouland, Andrew Huang, Anand Natarajan et al. · 1 citation · ⚡1

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.