We show that every multitape nondeterministic Turing machine can be simulated deterministically in subexponential time. Specifically, we show that the recent algorithms for $3$-$\mathsf{SAT}$ presented by OpenAI and Anthropic imply $\mathsf{NTIME}[t]\subseteq\mathsf{DTIME}[2^{O(t \log \log t/\sqrt{\log t})}]$, and that a stronger consequence of their proof yields \[\mathsf{NTIME}[t] \subseteq\mathsf{DTIME}[2^{O(t /\sqrt{\log t})}]. \] More generally, we show that any subexponential time algorithm for solving circuit-CSPs transfers to a deterministic simulation of $\mathsf{NTIME}$ with the same savings. Our results follow from new generalizations of Cook--Levin, which may be of independent interest.
Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan
原文摘要
We give an exposition of a recent proof of the Aaronson-Ambainis conjecture, which states that every degree-$d$ polynomial $p : \{0,1\}^n \to [0,1]$ has a variable of influence at least $\mathrm{poly}(\mathrm{Var}(p)/d)$. This implies that quantum query algorithms for decision problems can be efficiently simulated classically on most inputs. It also yields a near-equivalence between the status of the $\mathsf{BPP}$ vs. $\mathsf{BQP}$ problem in the random oracle and unrelativized worlds. We organize the proof around four main steps and discuss how each connects to the literature on the analysis of boolean functions and probabilistic combinatorics. To bring out the key ideas, we do not optimize parameters, and our presentation yields weaker exponents than the original. $\textbf{Authors' note.}$ The proof was discovered by David Turturean using a research system developed at Physical Superintelligence (PSI), in combination with a non-public Anthropic model. The proof was then shared with the authors, who worked to understand it and prepare this exposition. Anthropic's public models were used in this process. The authors did not receive financial compensation from Anthropic or PSI. This article is not intended for publication at a conference or in a journal.