显示为NP的完整问题
从NP-Complete上的维基百科条目：
“证明某个新问题是NP完全的最简单的方法是首先证明它是在NP中，然后将一些已知的NP完全问题归结为NP”
我很确定我明白这一点：如果我有一个问题，我可以证明它是NP-Complete，如果我：
表明它是在NP中（可以在非确定性图灵机上以多项式时间验证问题的解决方案）
证明已知为NP-Complete的问题可以“减少”到新问题中
所以，我的问题是，如何证明第一个NP完全问题是NP完全的？ 有一段时间，已知的NP完全问题的集合一定是零，并且这将使得在上述过程中不可能采取步骤2。
这让我觉得有一种我不知道的证明方法。 要么是这样，要么是由于缺乏已知的多项式时间解决方案，因此对于某些问题可能会“假设”整个NP完全属性。 （实际上，写过这些，如果是这种情况，我不会感到惊讶，但是我希望以某种方式反馈一些guru反馈）。
库克定理
类NP可以被定义为在多项式时间内由非确定性图灵机确定的问题类。 这个定理表明，通过用布尔公式对任何非确定性图灵机的操作进行编码， SAT是NP完全的，这样当且仅当该公式是可SATF时，机器才会接受。
历史上讲，NP完全性的概念是在Richard Karp的开创性论文（组合问题中的可减少性）中引入的，他定义了NP完全性，使用了Cook的定理，并且在一个大镜头中证明了21个NP完全问题。
为了给你提供证明的精髓（这是几页在Garey＆Johnson's Computers和Intractibility中的难题）：
任何计算问题都可以表示为图灵机。
可以将图灵机作为一个逻辑问题来表达，从而满足一定的复杂性约束。
因此，如果你可以在多项式时间内解决逻辑问题，你可以用多项式时间解决图灵机问题。
这一点（以及其他一些考虑）表明，如果您可以在多项式时间内解决逻辑问题，则可以在多项式时间内解决任何NP问题。 这就是NP完全的定义，因此逻辑问题是NP完全的，可以用作其他问题的基础。
使用的逻辑问题称为可满足性（Satisfiability）（通常缩写为SAT）。 给定一系列形式的条款（A或非B或非C）（由逻辑或命题连接的任意数量的命题和否定命题组成的条款）是否存在将命题的真值赋值给所有命题这些条款是真的吗？
NP完整性是一个明确的属性。 你对于NP完全问题的怀疑的唯一原因是你认为你可以减少另一个NP完全问题，但是还没有设法找到一个方便的问题或者得到一个证明。
问题不在于是否存在NP完全问题，或者如何证明问题是NP完全的，但这意味着什么。 目前还没有人提出一个多项式时间算法来解决NP完全问题，没有人证明这种算法不可能存在。 无论P = NP，我们当然没有很好的算法来解决任何NP完全问题。
这是克莱浦基金会的千年问题之一，所以如果你能提出一个证明，这个证明已经在一些非常聪明的人身上徘徊好几年了，那么你就有一百万美元了。
链接地址: http://www.djcxy.com/p/39967.html