algorithm - 所有 NP 问题的上限

Question

为什么所有 NP 问题都可以在 O(2^(n^k)) 内解决，也就是 EXPTIME？

其中 n^k 是输入大小 n 的多项式函数，并且可以取决于问题的大小。(k >= 0)

Answer 1

如果您可以采用一个候选解决方案并在多项式时间内检查它是否是正确的解决方案，那么问题就在 NP 中。所以测试一个解决方案的复杂度是 O(n^k)。

由于候选人可以被测试 O(n^k) 时间，它不能占用超过 O(n^k) 的空间。

有 2^(n^k) 个可能的候选对象，因此每次检查并测试它们需要 O(2^(n^k) * n^k)时间。

我怀疑这是否等同于 O(2^(n^k))，但它仍然在 EXPTIME 中。

事实上，它在 EXPTIME 的子类中，称为 P-SPACE。