所有NP的完整问题如何类似？

Question

我正在阅读一些证明给定问题的证明是NP完成的。证明技术有以下步骤。

1. 证明当前的问题是NP，即给定证书，证明可以在多项式时间内进行验证。
2. 采取任何已知的NP完整问题（调用“轻松”）并减少 全部它的实例 很少 给定问题的实例（调用“硬”）。请注意 不是 必然是1：1映射。
3. 证明可以在多项式时间内进行以上还原。

一切都很好。这些知识是否正确“如果您可以在多项式时间解决任何NP完整问题，那么所有NP完整问题都可以在多项式时间内解决”？

如果是的，那么根据上述证明技术，可以说“简单”问题可以在多项式时间内解决，这意味着如何在多项式时间内解决“硬”？我在这里想念什么？还是这是真的，“硬”问题也可以减少到“简单”问题？

Answer 1

您的问题似乎是因为您没有立即确信当前的问题并不难。当前的问题不会比任何NP完整问题都难，因为它在NP中。

如果您想确信NP完整性的概念甚至存在（即可以将NP中的任何内容都减少到NP完整问题），则应研究 Cook-Levin定理 哪个说明SAT是NP完整的。

由于NP完整性指出了减少目标的目标 任何 NP中的问题，证明是通过编码图灵机来起作用的，这是原始问题作为公式的验证者。当且仅当存在一个可以让图灵机接受的输入时，此公式才能满足。您可以原则上使用此证明来减少当前的问题，然后通过多项式时间减少的传递性来解决其他NP完整问题。

（实际上，我只想在评论中添加到库克levin定理的链接，但这是我的第一个stackexchange帖子，我认为它还没有让我发表评论。）

Answer 2

您对减少的方向感到困惑。因此，让我解释如何争论。

您有一种语言，例如$ l $，您想证明它是NP完整的。首先，您可以通过找到良好的证书来显示NP中确实是在NP中。因此，您可以通过显示NP硬度来留下。这可以通过减少一些NP完整语言$ L_ text {npc} $来完成。 至 您的语言$ l $，由poly time 多一减少. 。这意味着您定义一个poly time函数，该函数将$ l_ text {npc} $映射到$ l $的Yes-Instance，并将其映射到$ l_ text {npc} $的否定词$ L $。

由 传递性 在多个降低的poly Time中，NP中的每种语言现在都可以减少到$ l $（绕过$ l_ text {npc} $）。另一方面，如果存在决定$ l $的确定性poly Time算法$ a $，我们可以通过首先将其减少到$ L $，然后询问$ a $，在多项式时间内确定NP的每种语言。

看来您只是朝错误的方向思考。您称之为“简单”的问题可以通过减少和所谓的“硬”问题来解决。首先，这是奇怪的误导术语，其次，这可能是相反的。

Answer 3

给定一个$ a subset mathbb r $，您如何证明$ a $是套装$ a $的最大元素？有两个步骤：

1. 在$中显示$ a 。
2. 证明对于任何$ b a $，$ b leq a $。

如果$ a，b $是Set $ a $的最大元素，则将条件2两次（对于$ a $和$ b $）应用，您会得到$ a leq b leq a $。在$ mathbb r $中，这意味着$ a = b $，一组只能具有最大的元素。

---

现在，$ a^{ ast} $和$ leq $替换为$ a^{ ast} $。为了表明$ l $是NP填充，有一些步骤：

1. 证明 Mathsf {np} $中的$ l 。
2. 证明对任何$ l' in atmathsf {np} $，$ l' leq l $。这种情况称为NP硬度。

如果$ l，m $是两种NP完整语言，则应用条件2两次，您得到$ L leq m leq l $。这意味着问题是等效的：如果您能够解决$ l $，那么您可以解决$ m $，反之亦然。与Reals不同，$ L neq m $可能是的。令$ l sim m $表示$ l leq m leq l $。您可以证明这是一个等价关系。

---

锻炼。

假设$ m $是NP算法，而$ l sim m $。证明$ l $是NP完整的。

1. 证明 Mathsf {np} $中的$ l 。

   由于$ m $在NP和$ L leq m $中，因此识别$ L $的机器只能使用减少。

2. 证明对任何$ l' in atmathsf {np} $，$ l' leq l $。

   由于$ m $是np-hard，因此$ l' leq m $。由于我们知道$ m leq l $，因此通过传递性$ l' leq l $。

---

因此，如果两种语言是NP完整的，则它们是等效的。如果语言等于NP完整语言，则它也是NP完整的。

Answer 4

这里似乎有两个误解。

1. “简单”和“硬”：如果有的话，那是相反的。给定的问题是“容易”（我们不知道它的复杂性），另一个是 已知 要艰难。
2. “减少 全部 它的实例 很少 给定问题的实例“：重点是误导性的。降低的价值范围的大小并不重要。核心是，减少的实例保留了实例是否是肯定的。换句话说，NPC问题的实例是当且仅当其还原图像是给定问题的是的实例时，是一个实例。

然后，您要做的是证明您可以通过将其实例映射到给定的实例（在多项式时间）并解决这些问题来解决问题。因此，严重的问题不能比给定的问题更难。同等地，给定的问题至少与严重问题一样困难。 quod erat示范。