pipette
ESEspañol

Simulating Nondeterministic Turing Machines in Subexponential Deterministic Time

Carmen Strassle, Bernardo Subercaseaux

PreprintBold claims, read criticallyClaims a big step

In the authors' words

We show that every multitape nondeterministic Turing machine can be simulated deterministically in subexponential time. Specifically, we show that the recent algorithms for - presented by OpenAI and Anthropic imply , 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 with the same savings. Our results follow from new generalizations of Cook--Levin, which may be of independent interest.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.