Skip to content

Consequences of Polylogarithmic Membership Comparability for SAT

Sep 2026 · arXiv.org · Vol abs/2609.34952 · 0 citations · 29 references
Computer Science

TL;DR

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 between the randomized regimes.

Abstract

We study the consequences of membership comparators that exclude one possible membership vector, deterministically or with a relative advantage over uniform guessing. For every polynomially bounded arity, a randomized polynomial-time comparator of error at most $(1-1/poly(n))2^{-t}$ gives $ NP/ poly\cap coNP/ poly$ recognition with common advice. The proof uses limited independence, polynomial occurrence certificates, and a self-contained positive-relation advice transfer. For SAT at arity $O((\log n)^d)$, both this relative-gap hypothesis and deterministic comparability imply $PH=S^{NP}$, the uniform bound $PH\subseteq BPTIME(2^{O((\log n)^{d^2})})$, and symmetric verification with polynomial-length certificates and an oracle-free deterministic $2^{O((\log n)^d)}$ predicate. Polynomial-advice deterministic decoding has the same exponent $d$. Applying the randomized simulation to an unconditional diagonal language yields, for every fixed $\varepsilon>0$, $\mathrm{BPP}\subsetneq BPTIME(2^{O((\log n)^{d^2+\varepsilon})})$, without advice. The larger clock remains subexponential under every fixed number of self-compositions. A layered oracle satisfies deterministic comparability and $NP^O=coNP^O$ but excludes randomized NP algorithms with smaller logarithmic power, establishing a relativized limit on the SAT exponent $d$. This expanded version also 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 between the randomized regimes. Under deterministic comparability, uniform deterministic promise-unique search additionally gives $UEXP=EXP$. The ordinary second-level collapse $PH=\Sigma_2^p$ for $d>1$ remains unproved.

View source

Similar papers

Sep 2026

Linear Certificates for Membership Comparability, Quadratic Barriers for Selectors

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).

Sebastian Ben Daniel · 1 citation
Sep 2026

An exponential lower bound for the bit pigeonhole principle in resolution over parities

Resolution over parities, $\mathrm{Res}(\oplus)$, is the characteristic-two version of resolution over linear equations: clauses are disjunctions of affine equations over $\mathbb F_2$. Superpolynomial size lower bounds were previously known only for restricted refutations: tree-like, regular, or of bounded depth. We p...

Kamil Braun · 2 citations · ⚡2
Preprint Nov 2026

A Little Derandomization Goes a Long Way: Unconditional Circuit Lower Bounds using Low-Degree PIT

We prove unconditionally that either NE contains a language requiring Boolean circuits of size at least $2^n/(2n)$, or $VP^0_{\mathbb{Z}}\ne VNP^0_{\mathbb{Z}}$, a constant-free version of Valiant's conjecture over the integers. The Boolean alternative implies that $NP\not\subseteq SIZE[n^k]$ for every constant $k\ge1$...

Nikolai Chukhin, Karthik Gajulapalli, A. Golovnev et al. · 0 citations
Sep 2026

Constant-Probability Witness Isolation Implies NP in P/poly

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 · 1 citation
Preprint Oct 2026

Near-Inverse-Linear Barriers for Explicit Affine Witness Isolation

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

Sebastian Ben Daniel · 0 citations
Preprint Oct 2026

No Size-Preserving Amplification with Quantum Advice

Marriott and Watrous showed that quantum Merlin--Arthur games admit generic error reduction without increasing witness size [Computational Complexity, 2005]. In this work, we show that this state-size-preserving amplification property does not hold for polynomial-time quantum computation with quantum advice. In particu...

Shih-Han Hung, Han-Hsuan Lin · 0 citations

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