arXiv 论文证明非确定性图灵机可在亚指数确定性时间内模拟
Simulating Nondeterministic Turing Machines in Subexponential Deterministic Time
搞理论的朋友可以看看这篇：作者把 OpenAI 和 Anthropic 新的 3-SAT 算法接过来，推出了 NTIME 能被确定性机器以 2^{O(t/√log t)} 模拟，这可是 P vs NP 附近的核心问题。论文的关键新工具是 Cook–Levin 归约的推广，做复杂度和 SAT 求解器研究的人值得一读。
一篇新的 arXiv 论文（编号 2611.11832）证明：任何多带非确定性图灵机都可以在亚指数时间的确定性图灵机上模拟。具体结论是，基于 OpenAI 和 Anthropic 最近提出的 3-SAT 算法，可以推出 NTIME[t]⊆DTIME[2^{O(t log log t/√log t)}]；利用其证明的更强推论可达到 NTIME[t]⊆DTIME[2^{O(t/√log t)}]。
技术核心是对 Cook–Levin 归约的新推广，作者指出这一推广本身可能具有独立的理论价值。论文还给出更一般的结论：任何求解 circuit-CSP 的亚指数时间算法，都可以转化为对 NTIME 的确定性模拟，并保持同样的指数改进。
这一结果触及复杂性理论中时间层级与 P vs NP 相关的核心问题——非确定性计算能否被确定性计算高效模拟。虽然结论来自抽象的理论分析而非直接可用的算法，但对研究 SAT 求解器、参数化复杂度与指数时间假设（ETH）边界的理论研究者具有直接参考价值。
Simulating Nondeterministic Turing Machines in Subexponential Deterministic Time
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.
本条情报归属 AITOP「论文」核心追踪栏目。涉及核心实体与技术议题包括：NTIME、Cook-Levin、3-SAT、计算复杂性，读者可通过下方标签进入对应专题页查阅历史脉络与关联对比。
信源核验说明：本文原始信息发布自一手权威信源「arXiv: Anthropic」（Tier-1 一手发布），具备高确定性参考价值。