指数时间假设被证伪

如果你有一个包含 n 个布尔变量的表达式，找出是否存在某种变量取值赋值使该表达式为真需要多长时间？有一个明显的上界：通过穷举搜索，尝试将每个变量设为真或假的所有可能方式，你可以在 2n 步内找出答案。 对于特定问题，你通常可以比穷举搜索做得更好，但你总是能做得更好吗，即使在最坏情况下？Monien–Speckenmeyer 分支算法发表于 1985 年，比穷举搜索更高效，但它仍然需要指数时间。 3-SAT 布尔可满足性问题（SAT）询问是否存在某种变量取值赋值使一个合取范式（CNF）形式的布尔表达式可满足。k-SAT 问题是 SAT 的特例，其中没有任何子句包含超过 k 个变量。2-SAT 问题可以在多项式时间内求解，但 3-SAT 问题的情况尚不清楚。 3-SAT 问题是 NP 完全的，因此如果存在求解 3-SAT 的多项式时间算法，那么每个 NP 问题，包括完整的 SAT 问题，都可以在多项式时间内求解，即 P = NP。 上面提到的 Monien–Speckenmeyer 算法可以在 O( |F| φn ) 时间内求解 3-SAT 问题，其中 |F| 是输入公式的长度，φ 是黄金比例。现在 φ < 2，因此这比穷举搜索更好，但运行时间在变量数 n 上仍然是指数的。 ETH 指数时间假说（ETH）声称 3-SAT 需要指数时间，这将意味着 P ≠ NP。Anthropic 和 OpenAI 都发表了证明 ETH 为假的论文。P = NP 的状态仍然未知：虽然 3-SAT 不需要指数时间，但据任何人所知，它仍然需要超过多项式时间。 昨天 Shiva Kintali 发布了《ETH 为假的简化证明》。该论文的摘要说 对于每个固定的 ε > 0，我们给出一个确定性的 3-SAT 算法，在 n 个变量和 m 个子句上使用 Cε(n + m + 1)cε 2εn 位运算，反驳了 ETH。我们对 OpenAI 证明的简化阐述结合了稀疏化、有界出现、谱替换和有理插值。 相关文章 - 通过可满足性求解进行机器学习 - 将八皇后问题表述为 SAT 问题 - 使用 Z3 SAT/SMT 求解器的经验教训