Hoo*_*lum 5 algorithm code-analysis np
我知道他们的完全对应物意味着NP - 完全是NP问题中最难的,并且共同NP完全意味着共同NP问题中最难的但是两者之间的区别是什么？我的教科书上写着"是的,没有被逆转",这并没有给我留下那么多线索.
小智 13
只是为了补充其他人所说的内容（因为我自己发现这令人困惑），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 会令人惊讶，因为这意味着我可以给你一些证据，你可以快速检查它并发现我是对的。
And*_*dyG 10
当你想证明一个问题的难度,你必须把它变成一种叫做决策问题,这意味着"是/否"的答案类型的问题.例如,在Set Cover中,我们可能会问"我们可以仅使用X子集覆盖所有元素吗？" 其中X是一些任意数字.我们可以证明NP中存在这个问题,因为它的解决方案很容易验证; 你提供X子集,我检查是否所有元素都包含在多项式时间内.如果我们能够有效地回答对决策问题回答"是",那么我们可以最小化X,从而有效地解决整个Set Cover问题(从而证明P = NP).
Co-*(Co-NP,Co-NP-complete)侧重于对补充决策问题回答"否".例如,Set Cover的补充决策问题是" 对于X子集的每个组合,是否不可能涵盖所有元素？" 对这个问题回答"否"需要你提供一个反例.
总结:NP关注某些决策问题的"是"答案.Co-NP关注的是同一但补充的决策问题的"否"答案.
NP是一类决策问题，有多项式时间算法可以验证给定适当证书的情况下
\n\nCoNP是一类决策问题，其中存在多项式时间算法，可以在给定适当证书的情况下验证“否”实例。
\n\n我们不知道 coNP 是否与 NP 不同。
\n\ncoNP 中的每个问题都有一个 NP 中的问题，反之亦然。例如，SAT 问题询问“是否存在使该公式计算结果为 True 的布尔赋值？”。coNP 中的补数问题问道：“所有布尔赋值是否都会使该公式计算结果为 False？”
\n