arXiv 论文证明非确定性图灵机可在亚指数确定性时间内模拟

一篇新的 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）边界的理论研究者具有直接参考价值。