logo标签列表

第一个NP完全问题如何被证明为NP完全问题？

computer-sciencenp-complete
32
从 NP-Complete 的维基百科条目中得到的信息：
“证明某个新问题是 NP-完全问题的最简单方法是首先证明它在 NP 中，然后将一些已知的 NP-完全问题归约到该问题。”
我很确定我理解了这个概念：如果我有一个问题，我可以通过以下步骤展示它是 NP-完全问题：
1.展示它在 NP 中（问题的解可以在非确定性图灵机上以多项式时间验证）； 2.展示一个已知为 NP-完全问题可以被“归约”为新问题。
那么我的问题是，第一个 NP-完全问题是如何被“证明”是 NP-完全的？曾经，已知的 NP-完全问题集合可能为零，这将使得无法使用上述过程中的步骤 2。
这让我想到是否存在另一种我不知道的证明方法。或者，由于缺乏已知的多项式时间解决方案，对于某些问题，整个 NP-完全属性可能被“假定”。（事实上，写下这篇翻译后，我不会感到惊讶，但我希望得到一些大师的反馈）。
3
你的第二步做反了（我已经改正了）。仅仅把你的问题简化为NP完全问题是不够的，你需要将一个NP完全问题简化为你的新问题。（否则，你并没有真正展示出你的问题和原始的NP完全问题一样难。） - cjm
相关：https://cs.stackexchange.com/questions/42547/the-initial-np-complete-problem - johan
2个回答
33

库克定理

NP类问题可以定义为由非确定性图灵机在多项式时间内可解决的问题集合。该定理通过将任何非确定性图灵机的操作编码为布尔公式，以使机器接受当且仅当该公式是可满足的方式来表明SAT是NP完全问题。

从历史角度看，NP完全性概念是由理查德·卡普(Richard Karp) 的开创性论文(组合问题之间的可约性)引入的，他在其中定义了NP完全性，使用了库克定理，并一次性证明了21个问题是NP完全的。

6
为了让您了解证明的精髓（在Garey＆Johnson的《计算机和难题》中，需要数页才能理解）：
任何计算问题都可以表示为图灵机。
可以将图灵机表示为逻辑问题，满足某些复杂性约束条件。
因此，如果您可以在多项式时间内解决逻辑问题，则可以在多项式时间内解决图灵机问题。
这（以及其他一些考虑因素）表明，如果您可以在多项式时间内解决逻辑问题，则可以在多项式时间内解决任何NP问题。由于这是NP完全的定义，因此逻辑问题是NP完全的，并可用作其他问题的基础。
使用的逻辑问题称为可满足性（通常缩写为SAT）。给定一系列子句，形式为（A或not-B或not-C）（由任意数量的命题和命题的否定组成，由逻辑或连接），是否存在真值分配使所有子句都为真？
NP完全性是一个明确定义的属性。您对问题是否为NP完全的疑问只是因为您认为可以将另一个NP完全问题归约到它，但尚未找到方便的问题或推导出证明。
问题不在于NP完全问题是否存在，或如何证明问题是NP完全的，而在于其含义。迄今为止，没有人能够提出多项式时间算法来解决NP完全问题，也没有人证明这样的算法不存在。无论P = NP与否，我们都没有好的算法来解决任何NP完全问题。
这是Claypool基金会的千年难题之一，因此如果您能提出一个已经困扰很多聪明人多年的证明，那么您将获得一百万美元的奖励。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接