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

Question

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

<！>“证明一些新问题是NP完全的最简单的方法是首先证明它是在NP中，然后将一些已知的NP完全问题减少到它<！>

我很确定我理解这一点：如果我遇到问题，我可以证明，如果我：

，那就是NP-Complete

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

2. 显示已知为NP-Complete的问题可以 '减少'到新问题

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

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

Answer 1

Cook's Theorem

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

从历史上看，NP-completeness的概念是在Richard Karp的开创性论文中引入的（ 组合问题中的可还原性 ），他定义了NP完全性，使用库克定理，并在一个重要的事件中证明了21个问题NP完全。

Answer 2

为了给你证明的本质（这是Garey <！> amp; Johnson的计算机和不兼容性的几页难度）：

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

可以将图灵机表达为逻辑问题，满足某些复杂性约束。

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

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

使用的逻辑问题称为可满足性（通常缩写为SAT）。鉴于形式的一系列条款（A或非B或非C）（由任意数量的命题组成的条款和通过逻辑或连接的命题的否定），是否有一个真值的赋值给所有的命题条款是真的吗？

NP-completeness是一个明确定义的属性。你对NP完全问题有疑问的唯一原因是你认为你可以减少另一个NP完全问题，但是还没有设法找到一个方便的问题或者得到证据。

问题不在于是否存在NP完全问题，或者如何证明问题是NP完全的，但这意味着什么。目前还没有人产生多项式时间算法来解决NP完全问题，没有人证明这样的算法不存在。无论P = NP，我们当然没有很好的算法来解决任何NP完全问题。

这是Claypool基金会的千禧年问题之一，所以如果你能拿出一个已经躲过一些非常聪明的人很多年的证据，那么你就有一百万美元。