NP完全与NP硬

Question

我必须检查我的逻辑是否在正确的道路上。

NP -HARD：这是NP类中最难的问题。如果对这些问题有一个有效的算法，那么对于NP类中的每一个问题都有一个算法。

NP完全：这是NP类中最难的问题，而且如果您解决了其中的一个问题，就可以解决NP类中的任何问题。因此，NP完全问题是一个NP难问题.

库克定理：如果SAT( NP )有一个多项式时间算法，那么NP类中的每一个问题也是如此。

现在，假设我们必须证明CDP(集团决策问题)是NP完全。

->Step 1:证明CDP在NP类中。它属于NP类，因为证明程序可以生成对是输入的证明，这将使验证器能够检查它是否为CDP (有一个大小为k的团)。

->Step 2:证明CDP是NP硬。为此，我们可以通过从子句构造一个图并提供k来将SAT转换为CDP，并将(G，k)提供给团子例程，以验证是否存在一个大小为k的团。如果它能在多项式时间内计算出这一点，那么SAT就有一个多项式时间算法，因为CDP有一个多项式时间算法，我们将SAT转换为CDP。因此，现在我们证明了，如果CDP有多项式时间算法，那么SAT也是如此。现在，如果我们能找到一个用于CDP的多项式时间算法，那么它就意味着对于SAT有一个多项式时间算法。这就意味着NP中的每一个问题都有一个多项式时间算法。

因此我们证明了CDP是NP完全。一旦我们在NP完全类中加入了CDP，现在我们又提出了一个新的问题来证明它是NP完全的，我们可以证明这个问题在NP中是存在的，然后我们可以证明如果对给定问题有一个有效的算法，这就意味着对于NP完全有一个有效的算法(正如我们已经将它添加到NP完全中一样)。然后，我们可以将这个问题转化为CDP/SAT，然后证明如果我们的问题有一个有效的算法，那么CDP/SAT就有一个算法，然后根据COOK定理，我们又得到了一个NP -硬问题(这里是CDP/SAT)的解，那么NP中的每个问题都有一个解。因此，我们再次证明了我们的问题是NP难的，现在它也属于NP，如前所述，它是NP完全。

因此，只要我们能将NP -硬类(本例中的SAT/CDP)中的一些问题转化为我们的问题，我们就可以在NP完全类中增加更多的问题，并且对我们的问题应该找到一种有效的算法，它可以间接地找到NP-硬问题的有效算法，并且根据库克定理，我们可以说，由于某些NP-硬问题有一个有效的算法，所以我们有一个有效的算法来解决NP中的所有问题。

Answer 1

你走在正确的道路上，但你的逻辑有点不完整。

你证明的一般结构是正确的:首先证明一个问题在NP中，然后证明这个问题是NP难的。这两部分信息一起证明了一个问题是NP-完全的。

你证明一个问题的证据是NP是不完整的。以下是在NP中证明问题的关键组件：

1. 把这个问题改写为一个可以用“是”或“否”来回答的决定问题。
2. 描述什么是“证书”。注意:证书是可以检查以验证决策问题答案的输出。对于CDP，它可以是构成k大小团的顶点和边的列表。
3. 证明了该证书可以在多项式时间内得到验证。

你证明NP难的证据是不完整的。下面是证明一个问题是NP难的关键组件：

1. 将已知NP困难问题的输入转化为您试图证明的问题的输入。
2. 证明了这种变换可以在多项式时间内完成。
3. 将你试图证明的问题的输出转化为已知NP-困难问题的输出。
4. 演示如何在多项式时间内完成此操作。
5. 证明，如果你得到了你想要证明的问题的答案，那么你就有了一个已知问题的答案。
6. 证明，如果你得到一个已知问题的答案，你有一个问题的答案，你想要证明。

只有通过满足这6个标准，你才能说你已经完全证明了一个问题是NP难的。

除了关于你的逻辑是合理的细节。如果你的意思是“可以在多项式时间内解决”，那么在说“有效”时要小心。