第一个NP完全问题如何显示NP完全？

Question

来自NP-Complete的维基百科条目:

"证明一些新问题是NP完全的最简单的方法是首先证明它是在NP中,然后减少一些已知的NP完全问题"

我很确定我理解这一点:如果我有问题,我可以证明它是NP-Complete如果我:

所以,我的问题是,第一个NP完全问题"被证明"是NP完全的吗？同时,已知NP完全问题的集合必须为零,这将使得在上述过程中不可能采用步骤2.

这让我觉得有一种不同的证明方法,我不知道.由于缺少已知的多项式时间解决方案,或者可能由于缺少已知的多项式时间解而对某些问题"假设"整个NP完全属性.(实际上,写完这篇文章后,如果是这样的话,我不会感到惊讶,但无论如何我都喜欢一些古茹反馈).

Answer 1

NP类可以定义为在多项式时间内由非确定性图灵机可判定的问题类别.该定理通过布尔公式对任何非确定性图灵机的操作进行编码,表明SAT是NP完全的,这样机器只有在该公式满足时才接受.

从历史上看,NP完全性的概念是在理查德卡普的开创性论文(组合问题中的可约性)中引入的,他在这篇论文中定义了NP完全性,使用了库克定理,并在一个大的镜头中证明了21个问题NP完全.

Answer 2

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

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

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

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

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

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

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

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

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