我对 NP-complete 了解不多，但在这里和那里阅读它。我正在学习的《算法简介》一书指出：“尽管尚未找到针对 NP 完全问题的有效算法，但没有人证明不存在针对一个人的有效算法。” 我只是想知道，一个人怎么知道他们拥有的算法不是最有效的……如果那是所有算法中最有效的一种？
谢谢，
山姆
问问题
525 次
2 回答
2
好问题。我很好奇这个问题的答案是什么，但这是我的尝试。
很难知道是否存在比您想出的更好的算法（如果您确实知道，那么您的算法将是更好的算法）。那么问题就变成了你什么时候应该停止尝试寻找更好的算法。主要方法包括为问题提出下限，然后依次使它们越来越强。
假设你是一名研究人员
进一步研究这个问题的一个好的开始是考虑基于标准比较的排序问题。我们得到一个包含 n 个元素的列表，并希望对其进行排序。所以最糟糕的算法，就是想出所有的n！列表，并检查哪个已排序。然后更直观的方法是使用冒泡排序之类的方法，即 O(n^2)。我们想知道我们是否还能做得更好。好吧，假设我们使用分而治之，我们提出了 O(n log n) 的合并排序。现在我们有兴趣知道合并排序是否不是最有效的。所以我们花更多的时间去想一个更好的算法，但想不出一个。所以我们感到沮丧，并改变我们的方法并考虑证明没有比 O(n log n) 更好的比较排序。
现在直观地说，一个简单的下限是 O(n)，仅仅是因为为了对列表进行排序，我们至少需要 O(n) 时间来读取它。但是，让我们尝试改进这个下限。如果您以前没有见过，看看您是否可以提出对 O(n log n) 的下限改进。如果您无法获得它，请查看这篇出色的文章，证明 n log n 是比较排序的下限：http ://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/19-lowerbounds .pdf
现在让我们开始思考 NP Complete 问题。考虑顶点覆盖问题（图 st 中是否存在一组 k 个顶点，每条边都与至少一个顶点相关），它是 NP Complete。我们提出了最直观的蛮力方法来解决它（使所有（n 选择 k）个顶点选择并测试每个可能的解决方案）。现在的问题是，是否存在更有效的东西？好吧，经过很多努力，假设我们不能更快地想出任何东西。所以我们采取与以前相同的方法，试图找到好的下界并不断改进它们。显然 O(n) 是一个下界，但我们无法证明 O(n 选择 k) 次下界（如果我们确实证明了这样的下界，那么蛮力是解决顶点覆盖的最佳方法）。所以我们休息一下，然后处理其他问题。
然后有一天我们正在研究图上的最大独立集问题（是否存在由 k 个顶点组成的集合 S，使得 S 中没有两个顶点是相邻的）。我们提出了一个蛮力解决方案，但我们想知道这是否不是最有效的算法。然而，我们不能想出更好的东西，也不能想出一个严格的下限，所以我们不能说是否存在更快的东西。
然后很多天后，我们看到这些问题实际上是等价的，从某种意义上说，一个有效的算法为另一个提供了一个有效的算法：http ://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/npcomplete .pdf
因此，虽然我们不知道顶点覆盖或独立集的算法是否最有效，但我们可以通过将问题减少到彼此来比较相对难度，这样如果我们找到一个好的算法，我们就可以应用那是另一个问题。
TL;博士
本质上，它归结为费曼方法：
严肃地说，为了表明我们的算法是或不是最好的：
- 找到更好的算法或证明它的存在（可能通过简化为您见过的另一个问题）
- 证明不存在更好的算法。可能通过找到我们的算法实现的下界。
如果以上两个都失败了，而不是明确地回答，试着想出你正在解决的问题有多困难的概念，方法是查看你可以减少的问题并考虑它们的难度。
于 2013-03-21T02:45:26.847 回答
1
您引用的陈述是指计算机科学中最大的未解决问题之一，即是否P = NP。
NP 是可以快速验证的问题（在多项式时间内），而 P 是可以快速找到解决方案的问题（在多项式时间内）
简单地说，如果 NP 完全问题有一个“有效”算法，那么 P = NP
在所有这些讨论中，“高效”和“快速”几乎总是意味着多项式时间。
因此，要回答你的问题，一旦你有了一个非多项式算法，你就会知道它效率不高（在上面的上下文中）。
于 2013-03-21T02:56:08.600 回答