所有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.