我知道它们的完全对应关系意味着NP-complete问题是NP问题中最难的问题，而co-NP-complete问题是co-NP问题中最难的问题，但两者之间有什么区别呢？我的教科书说：“肯定和否定被颠倒了”，这并没有给我留下太多线索。
NP和co-NP有什么区别？
16
- jantristanmilan
2
相关链接：https://math.stackexchange.com/questions/361422/why-isnt-np-conp - Ciro Santilli OurBigBook.com
同时 https://math.stackexchange.com/questions/2334429 - logi-kal
3个回答
17
当你想证明一个问题的难度时，你需要将其转化为决策问题，也就是“是/否”类型的问题。例如，在集合覆盖问题中，我们可能会问“是否可以仅使用X个子集覆盖所有元素？”其中X是某个任意数。我们可以证明这个问题存在于NP中，因为它很容易验证；你提供X个子集，我检查所有元素是否在多项式时间内都被覆盖。如果我们能有效地回答“是”这个决策问题，那么我们就可以最小化X，从而有效地解决整个集合覆盖问题（从而证明P=NP）。
Co-*（Co-NP、Co-NP-complete）专注于回答补充决策问题的“否”。例如，集合覆盖问题的补充决策问题将是“对于每个组合的X个子集，是否不可能覆盖所有元素？”回答“否”要求你提供一个反例。
总之：NP关注某些决策问题的“是”答案。Co-NP则专注于同样的决策问题的“否”答案，但是是对应的补充问题。
Co-*（Co-NP、Co-NP-complete）专注于回答补充决策问题的“否”。例如，集合覆盖问题的补充决策问题将是“对于每个组合的X个子集，是否不可能覆盖所有元素？”回答“否”要求你提供一个反例。
总之：NP关注某些决策问题的“是”答案。Co-NP则专注于同样的决策问题的“否”答案，但是是对应的补充问题。
- AndyG
4
你的意思是使用相同的多项式验证器来回答这两个问题吗？一个是检查证书是否为解决方案，另一个是检查它是否为反面问题的解决方案，即证明其为反例。如果是的话，这种文字游戏的目的是什么？ - Ahmad
@Ahmad：我们实际上不能使用相同的验证程序回答这两个问题。就像我们不确定 P = NP 一样，我们也不确定 NP = Co-NP。一个能够回答“是”NP问题的多项式验证程序可能无法轻松地回答补集决策问题的“否”。 - AndyG
3在你的例子中，似乎这样一个验证者可以回答两个问题。我想让你再添加一个例子来展示回答"不是"或其他问题并不容易。 - Ahmad
从维基百科关于Co-NP的解释中可以得知：如果一个决策问题X是co-NP类的成员，那么它的补集X就在复杂度类NP中。因此我认为，同样的验证器可以用来解决这两个问题。如果你将NP改为Co-NP并且取问题的补集，那么本质上就是同一个问题。我认为Co-NP很有用，可以表达提供“否定”答案的难度有多大，而不改变问题的定义（即取补集）。 - xuiqzy
13
其他人已经说了一些，我想再补充一点（因为我自己也感到有些困惑），NP = co-NP 的问题是询问是否每个决策问题都存在一个“yes”回答可以在多项式时间内检查，并且也存在一个“no”回答可以在多项式时间内检查。
这有点令人困惑，因此这里有一个例子：旅行商问题的决策形式（“给定图形G，是否存在长度为L或更短的路径，该路径至少访问每个顶点一次？”）属于NP：如果我说“是的，存在一条长度为L或更短的路径，该路径至少访问每个顶点一次”，那么我证明的方式是给你一条长度为L或更短且至少访问每个顶点一次的路径，你检查我的解决方案的方法是获取我的路径，检查它是否至少访问每个顶点一次，以及它的长度是否小于等于L。之所以该问题属于NP，是因为进行这种检查需要多项式时间（即非常快）。
该问题的补集将是“给定图形G，是否不存在长度为L或更短的路径，该路径至少访问每个顶点一次？”回答“否”表示基本上是与上述问题相同。我将会说“不，不存在长度为L或更短的路径（双重否定很令人困惑），该路径至少访问每个顶点一次。为了证明这一点，这里有一条长度为L或更短且至少访问每个顶点一次的路径。因此，在G中不存在长度为L或更短的路径，该路径至少访问每个顶点一次。” 当人们说任何NP问题的补集都属于co-NP时，这就是他们的意思。
那么，如果NP = co-NP，这意味着什么？它意味着如果一个问题属于NP（可以轻松检查“yes”答案），那么它也属于co-NP（可以轻松检查“no”答案）。
（再次强调，我们正在谈论问题本身，而不是问题的补集：我们已经知道任何NP问题的补集属于co-NP。我们正在讨论原始问题。）
但对于旅行商问题，这不是很明显：如果我说“否，G中没有长度为L或更短的路径，该路径恰好访问每个顶点一次”，我将如何证明这一点？当答案是“是”时，我可以轻松地向你证明这一点（只需给你路径，以便你自己检查即可）。但是如果我的答案是“否”，我们不知道有什么简单方法可以检查我是否正确。我只能说“相信我，我已经检查过了。”发现NP = co-NP会令人惊讶，因为这意味着我可以给你某种证明，并且你可以快速检查并看到我是正确的。
这有点令人困惑，因此这里有一个例子：旅行商问题的决策形式（“给定图形G，是否存在长度为L或更短的路径，该路径至少访问每个顶点一次？”）属于NP：如果我说“是的，存在一条长度为L或更短的路径，该路径至少访问每个顶点一次”，那么我证明的方式是给你一条长度为L或更短且至少访问每个顶点一次的路径，你检查我的解决方案的方法是获取我的路径，检查它是否至少访问每个顶点一次，以及它的长度是否小于等于L。之所以该问题属于NP，是因为进行这种检查需要多项式时间（即非常快）。
该问题的补集将是“给定图形G，是否不存在长度为L或更短的路径，该路径至少访问每个顶点一次？”回答“否”表示基本上是与上述问题相同。我将会说“不，不存在长度为L或更短的路径（双重否定很令人困惑），该路径至少访问每个顶点一次。为了证明这一点，这里有一条长度为L或更短且至少访问每个顶点一次的路径。因此，在G中不存在长度为L或更短的路径，该路径至少访问每个顶点一次。” 当人们说任何NP问题的补集都属于co-NP时，这就是他们的意思。
那么，如果NP = co-NP，这意味着什么？它意味着如果一个问题属于NP（可以轻松检查“yes”答案），那么它也属于co-NP（可以轻松检查“no”答案）。
（再次强调，我们正在谈论问题本身，而不是问题的补集：我们已经知道任何NP问题的补集属于co-NP。我们正在讨论原始问题。）
但对于旅行商问题，这不是很明显：如果我说“否，G中没有长度为L或更短的路径，该路径恰好访问每个顶点一次”，我将如何证明这一点？当答案是“是”时，我可以轻松地向你证明这一点（只需给你路径，以便你自己检查即可）。但是如果我的答案是“否”，我们不知道有什么简单方法可以检查我是否正确。我只能说“相信我，我已经检查过了。”发现NP = co-NP会令人惊讶，因为这意味着我可以给你某种证明，并且你可以快速检查并看到我是正确的。
- Matthew Tromp
6
NP是指那些决策问题的类别，对于这些问题，如果有合适的证书，就可以有一个多项式时间算法来验证“是”实例。
CoNP是指那些决策问题的类别，对于这些问题，如果有合适的证书，就可以有一个多项式时间算法来验证“否”实例。
我们不知道coNP是否与NP不同。
对于coNP中每个问题都有一个NP问题，反之亦然。例如，SAT问题是“是否存在一种布尔分配使得该公式评估为True？”相应的补问题位于coNP中，它问：“所有布尔分配是否都使该公式评估为False？”
我们不知道coNP是否与NP不同。
对于coNP中每个问题都有一个NP问题，反之亦然。例如，SAT问题是“是否存在一种布尔分配使得该公式评估为True？”相应的补问题位于coNP中，它问：“所有布尔分配是否都使该公式评估为False？”
- Adam Rosenthal
1
1没有必要证明Co-NP是多项式可证实的，因为这会导致Co-NP = NP。 - dato nefaridze
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接