Simulating Nondeterministic Turing Machines in Subexponential Deterministic Time
cs.CC
Submitted: 2026-11-09
Updated: 2026-11-09
Code: https://github.com/openai/math
License: http://creativecommons.org/licenses/by/4.0/
The gist: We show that every multitape nondeterministic Turing machine can be simulated deterministically in subexponential time.
Terminology
Abstract
We show that every multitape nondeterministic Turing machine can be simulated deterministically in subexponential time. Specifically, we show that the recent algorithms for 3 - presented by OpenAI and Anthropic imply [t] [2 O(t t/sqrt t)], and that a stronger consequence of their proof yields [t] [2 O(t /sqrt 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.
Sources
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?