arXiv:2611.11832 · v1

Simulating Nondeterministic Turing Machines in Subexponential Deterministic Time

首次提交 2026-11-09 11:49

版本更新 2026-11-09 11:49

雷达观测 2026-11-10 13:18

摘要

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.