algorithm - NP和co-NP有什么区别

Question

我知道他们的完全对应物意味着 NP - 完全是 NP 问题中最难的，而 co-NP-complete 意味着在 co-NP 问题中最难的，但两者之间有什么区别？我的教科书说“是与否是颠倒的”，这并没有给我留下太多线索。

Answer 1

当你想证明一个问题的难度时，你必须把它变成一个叫做决策问题的东西，这意味着一个“是/否”答案类型的问题。例如，在 Set Cover 中，我们可能会问“我们能否仅使用 X 个子集覆盖所有元素？” 其中 X 是某个任意数字。我们可以证明这个问题存在于 NP 中，因为它的解决方案很容易验证；你提供 X 个子集，我检查是否所有元素都在多项式时间内被覆盖。如果我们可以对决策问题有效地回答“是”，那么我们可以最小化 X，从而有效地解决整个 Set Cover 问题（从而证明 P=NP）。

Co-* (Co-NP, Co-NP-complete) 侧重于对补充决策问题回答“否”。例如，Set Cover 的补充决策问题将是“对于 X 个子集的每个组合，是否不可能覆盖所有元素？” 对这个问题回答“否”需要你提供一个反例。

总而言之：NP 关心的是对某些决策问题的“是”回答。Co-NP 关注的是对相同但补充的决策问题的“否”回答。

Answer 2

NP是一类决策问题，有一个多项式时间算法可以在给定适当证书的情况下验证“是”实例。

CoNP是一类决策问题，有一个多项式时间算法可以验证给定适当证书的“否”实例。

我们不知道 coNP 是否与 NP 不同。

对于 coNP 中的每个问题，NP 中都有一个问题，反之亦然。例如，SAT 问题询问“是否存在使该公式评估为 True 的布尔赋值？”。coNP 中的补码问题询问“是否所有布尔赋值都使该公式的计算结果为 False？”

Answer 3

只是为了补充其他人所说的（因为我自己发现这令人困惑），是否 NP = co-NP 的问题是询问是否每个决策问题都有可以在多项式时间内检查的“是”答案有一个可以在多项式时间内检查的“否”答案。

这有点令人困惑，所以这里有一个例子：旅行商问题的决策形式（“给定一个图 G，G 中是否有一条长度为 L 或更短的路径至少访问每个顶点一次？”）在 NP 中：如果我说“是的，有一条长度为 L 或更短的路径至少访问每个顶点一次”，我证明这一点的方法是为您提供一条长度为 L 或更短的路径，该路径至少访问每个顶点一次，并且检查我的解决方案的方法是走我的路径，检查它是否至少到达每个顶点一次，并且它的长度为 L 或更短。这个问题在 NP 中，因为做这个检查需要多项式时间（即它很快）

这个问题的补充将是“给定一个图 G，G 中是否没有长度为 L 或更短的路径至少访问每个顶点一次？” 对这个问题回答“否”与上面的问题基本相同。为了证明这一点，我会说“不，没有长度为 L 或更短的路径（双重否定会令人困惑）至少访问每个顶点一次。为了证明这一点，这里有一条长度为 L 或更短的路径可以访问每个顶点至少一次。因此，在 G 中没有长度为 L 的路径至少访问每个顶点一次是不正确的。这就是人们说任何 NP 问题的补码在 co-NP 中时的意思。

那么，如果 NP = co-NP 意味着什么？这意味着如果问题在 NP 中（您可以轻松地检查“是”答案），它也在 co-NP 中（您可以轻松地检查“否”答案）。

（重申一下，我们不是在谈论问题的补码：我们已经知道 NP 问题的补码在 co-NP 中。我们在询问原始问题。）

但是对于旅行商问题，这将如何工作并不明显：如果我说“不，在 G 中没有长度为 L 或更短的路径恰好访问每个顶点一次”，我将如何证明这一点？当答案是“是”时，我很容易向您证明这一点（只需给您路径，以便您自己检查）。但如果我的回答是“不”，就没有简单的方法（我们知道）来检查我是否正确。我只能说“相信我，我检查了所有这些”。发现 NP = co-NP 会令人惊讶，因为这意味着我可以给你一些证据，你可以快速检查它并确定我是对的。