computer-science - 如果我们“假设” P 不等于 NP，为什么 NP 可能等于 co-NP 背后的直觉

Question

如果我们“假设” P 不等于 NP ，这表明NP可能等于 co-NP 。

我搜索了很多，浏览了很多材料。我似乎不能很直观地理解为什么这可能是真的。如果有人可以引导我找到任何资源或帮助我直观地理解为什么这是真的，那将非常有帮助。

标签： computer-sciencecomplexity-theorynp

Answer 1

这是一种可能的直觉，鉴于我们尚未解决P与NP的问题，这可能会完全被误导。

复杂性类P可以被认为是以下陈述为真的所有问题：有一个布尔函数solveProblem使得

• solveProblem在多项式时间内以其输入的大小运行，
• x对于答案为“是”的任何输入，solveProblem(x)返回 true，并且
• x对于答案为“否”的任何输入，solveProblem(x)返回 false。

现在，让我们看一下NP的定义。这是一组问题，以下陈述为真：有一个布尔函数checkYesAnswer，使得

• checkYesAnswer在多项式时间内运行，
• 对于答案为“是”的任何输入x，有些y地方checkYesAnswer(x, y)返回真，并且
• x对于答案为“否”的任何输入，checkYesAnswer(x, y)始终返回 false。

那么， P和NP之间的区别在于，当您查看复杂性类P时，您只得到输入并且需要做出是/否决定，而在类NP中可能有一些辅助信息这可以帮助您做出是/否的决定。这使得P和NP的定义之间的区别非常大——在一种情况下，您需要解决问题，而在另一种情况下，您需要检查一些辅助信息是否对您有帮助。

现在，这是 co- NP的另一个等效定义。类 co- NP包含所有存在布尔函数的问题，checkNoAnswer使得

• checkNoAnswer在多项式时间内运行，
• x对于答案为“是”的任何输入，checkNoAnswer(x, y)始终返回 true，并且
• x对于答案为“否”的任何输入，可以选择返回 true的y位置。checkNoAnswer(x, y)

换句话说，NP和 co - NP的定义非常密切相关，唯一的区别是“是”和“否”的分支交换了。所以从这个意义上说，即使P ≠ NP ， NP和 co - NP可能相等仍然是合理的，因为我们基本上只是颠倒了“是”和“否”这两个词的角色。

也有充分的理由来了解为什么NP可能不是 co - NP。您可以将定义之间的区别想象如下：对于NP，如果存在具有某些y属性的某些属性，则答案是“是”，而对于 co- NP，如果所有 y东西都成立，则答案是“是”。而且由于 ∃ 和 ∀ 量词的工作方式不同，也许这里还有其他事情发生。