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) 的算法来决定