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

Question

我知道他们完整的同行意味着NP - 完全是 NP 问题中最难的，而 co-NP-complete 是指 co-NP 问题中最难的，但两者之间有什么区别？我的教科书说“是和否是相反的”，这并没有给我留下太多线索。

Answer 1

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

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

总而言之:NP 关注对某些决策问题的"is"回答。 Co-NP 关注的是对相同但互补的决策问题的“否”答案。