从 NP-Complete 上的维基百科条目：
“证明一些新问题是NP完全的最简单方法是首先证明它在NP中，然后将一些已知的NP完全问题简化为它”
我很确定我理解这一点：如果我有问题，我可以证明它是 NP-Complete 如果我：
证明它在 NP 中（可以在非确定性图灵机上以多项式时间验证问题的解决方案）
证明一个已知为 NP-Complete 的问题可以“简化”为新问题
所以，我的问题是，第一个 NP 完全问题是如何“证明”为 NP 完全的？有一次，已知 NP 完全问题的集合必须为零，这使得无法诉诸上述过程中的步骤 2。
这让我觉得有一种我不知道的不同的证明方法。由于缺乏已知的多项式时间解，对于某些问题，要么是这样，要么可能是整个 NP 完全属性被“假设”。（实际上，在写完这篇文章后，如果是这种情况，我不会感到惊讶，但无论哪种方式，我都希望得到一些大师的反馈）。
NP类可以定义为非确定性图灵机在多项式时间内可判定的一类问题。这个定理表明SAT 是 NP 完全的，它通过一个布尔公式对任何非确定性图灵机的操作进行编码，使得机器接受当且仅当该公式是 SATisfiable 时。
从历史上看，NP-completeness 的概念是在 Richard Karp 的开创性论文（Reducibility Between Combinatorial Problems）中引入的，他在其中定义了 NP-completeness，使用了 Cook 定理，并且一举证明了 21 个问题 NP-complete。
为了给你证明的本质（这是 Garey & Johnson 的Computers and Intractibility中的好几页）：
任何计算问题都可以表示为图灵机。
可以将图灵机表示为一个逻辑问题，满足一定的复杂性约束。
因此，如果你能在多项式时间内解决逻辑问题，你就可以在多项式时间内解决图灵机问题。
这（连同其他一些考虑）表明，如果您可以在多项式时间内解决逻辑问题，那么您可以在多项式时间内解决任何 NP 问题。这是NP完全的定义，因此逻辑问题是NP完全的，并且可以用作其他问题的基础。
使用的逻辑问题称为可满足性（通常缩写为 SAT）。给定一系列形式为（A or not-B or not-C）的子句（由任意数量的命题和由逻辑或连接的命题的否定组成的子句），是否存在对命题的真值分配，使得所有条款是真的吗？
NP 完全性是一个定义明确的属性。你怀疑一个问题是否是 NP 完全的唯一原因是你认为你可以将另一个 NP 完全问题简化为它，但还没有设法找到一个方便的问题或得到一个证明。
问题不在于是否存在 NP 完全问题，或者如何证明一个问题是 NP 完全的，而是这意味着什么。还没有人提出多项式时间算法来解决 NP 完全问题，也没有人证明这样的算法不存在。不管 P=NP，我们肯定没有好的算法来解决任何 NP 完全问题。
这是克莱普尔基金会的千年问题之一，所以如果你能拿出一个证明，让一些非常聪明的人多年来一直没有找到答案，那么你就有一百万美元。