上界上的所有NP问题

为什么所有NP问题地在O（2 ^（N^k））的解决，又名EXPTIME？上界上的所有NP问题

其中n^k为输入大小为n的多项式函数，并且可以依赖于问题的大小。（k> = 0）

2014-04-30 ginsunuva

如果您有指数时间，您可以枚举整个搜索空间。对于SAT来说，这意味着您可以尝试每种可能的值组合，以查看它们中的任何一个是否满足。 – senshin

未来，您可能希望在[计算机科学SE]（http://cs.stackexchange.com/） –

如果您可以选择一个解决方案并在多项式时间内检查是否是正确的解决方案，那么问题在于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-空间。

2014-04-30 21:16:46 zmbq

'2 ^（n^k）* n^k = 2 ^（n^k + k * log2（n））'，并且肯定存在一个m，使得对于足够大的n来说，n^k + k * log2（n）

回答