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

Question

来自维基百科关于 NP 完全问题的条目：

“证明某些新问题是 NP 完全问题的最简单方法是首先证明它是 NP 问题，然后将一些已知的 NP 完全问题简化为它”

我很漂亮确保我理解这一点：如果我有一个问题，我可以证明它是 NP 完全的，如果我：

1. 表明它是 NP 的（解决方案 问题可以在 多项式时间 非确定性图灵机）

2. 表明已知的 NP 完全问题可以是 “简化”为新问题

那么，我的问题是，第一个 NP 完全问题是如何“证明”为 NP 完全的？ 某一时刻，已知的 NP 完全问题集必须为零，这使得不可能诉诸上述过程中的步骤 2。

这让我觉得有一种我不知道的不同的证明方法。 或者，或者由于缺乏已知的多项式时间解，对于某些问题，整个 NP 完全性质可能被“假设”。 （实际上，写完这篇文章后，如果情况确实如此，我不会感到惊讶，但无论如何我都希望得到一些大师的反馈）。

Answer 1

库克定理

NP 类可以定义为可由非确定性图灵机判定的问题类在多项式时间内。 该定理通过布尔公式对任何非确定性图灵机的操作进行编码，表明 SAT 是 NP 完全的，当且仅当该公式是 SATisfiable 时，机器才会接受。

从历史上看，Richard Karp 的开创性论文中引入了 NP 完备性的概念（可归约性在《组合问题》）中，他定义了 NP 完全性，使用了库克定理，并一次性证明了 21 个问题是 NP 完全性的。

Answer 2

为了给你证明的本质（这是 Garey 和 Johnson 的计算机与难解性中的几页内容）：

任何计算问题都可以表示为图灵机。

可以将图灵机表示为逻辑问题，满足一定的复杂性约束。

因此，如果你能在多项式时间内解决逻辑问题，你就能在多项式时间内解决图灵机问题。

这（以及其他一些考虑因素）表明，如果您可以在多项式时间内解决逻辑问题，则可以在多项式时间内解决任何 NP 问题。 这是NP完全的定义，因此逻辑问题是NP完全的，并且可以用作其他问题的基础。

使用的逻辑问题称为可满足性（通常缩写为 SAT）。 给定一系列形式为（A或非B或非C）的子句（子句由任意数量的命题和命题的否定组成，通过逻辑或连接），是否存在对命题的真值分配，使得所有该条款属实吗？

NP 完整性是一个明确定义的属性。 您怀疑某个问题是否为 NP 完全问题的唯一原因是您认为可以将另一个 NP 完全问题简化为该问题，但尚未找到方便的问题或导出证明。

问题不在于是否存在 NP 完全问题，或者如何证明一个问题是 NP 完全问题，而在于这意味着什么。 尚未有人提出多项式时间算法来解决 NP 完全问题，也没有人证明这样的算法不存在。 无论是否P=NP，我们当然没有好的算法来解决任何NP完全问题。

这是克莱普尔基金会的千年难题之一，因此，如果你能提出一个多年来一直困扰一些非常聪明的人的证明，那么你将获得一百万美元。