1

NP 中的任何问题都可以在确定性的指数时间内解决,或者我们可以说 NP 中的任何语言都可以由运行时间为 2^O(n^k) 的算法决定,即 NP ⊆ EXP

通俗地说,我们只是尝试每一种可能的解决方案,然后再决定

但是,有一个简单的例子,我无法弄清楚我提出的想法有什么问题

这里是..

旅行商问题:给定一个无向图 G=(V,E) V=|n|

这是一个众所周知的 NP 完全问题,因此,确实属于 NP

我尝试分析运行时间..像这样:

我只是列出了所有可能的解决方案,并且有 (n-1) 个!总共可能的旅行

然后我检查它们中的每一个,每个可能的旅行都需要 O(n)

总运行时间为 O(n!)

它看起来不能以 2^O(n^k) 为界,即指数时间

这种分析的缺陷在哪里?

或者换句话说,我们如何解释旅行商问题确实可以通过运行时间 2^O(n^k) 的算法来决定

4

1 回答 1

2

注意

嗯!≤ n n = (2 log n ) n = 2 n log n ≤ 2 n 2

儿子!= 2 O(n 2 ),所以 n! ∈ 经验。

希望这可以帮助!

于 2013-11-19T17:44:14.307 回答