1

我正在研究 NP 课程，其中一张幻灯片提到：

It seems that verifying that something is not present is more difficult than verifying that it is present.
       ______                  _________
Hence, CLIQUE (complement) and SubsetSUM (complement) are not obviously members of NP.

是否曾经证明，CLIQUE 的补语是否是 NP 的一个元素？

另外，你有证据吗？

4

2 回答 2

2

实际上，这是一个悬而未决的问题！复杂性类co-NP由 NP 中所有问题的补集组成。现在不知道NP = co-NP，很多人怀疑答案是否定的。

正如 CLIQUE 是NP 完全的，CLIQUE 的补集是co-NP 完全的。（更一般地，任何NP 完全问题的补集都是co-NP 完全问题）。有一个定理，如果任何co-NP 完全问题在NP中，那么co-NP = NP，这将是一个巨大的理论突破。

如果您有兴趣了解更多相关信息，请查看关于co-NP的 Wikipedia 文章并在线查看更多资源。

于 2016-01-16T00:49:34.137 回答
1

这里的一般直觉：很容易证明一个图包含一个 N-clique：只要给我看这个 clique。很难证明没有 N 团的图实际上没有 N 团。你打算利用图表的什么属性来做到这一点？

当然，对于某些图族，您可以——例如，边缘足够少的图不可能有这样的派系。完全有可能所有图都可以围绕它们建立类似的证明，尽管这会令人惊讶——几乎和 P=NP 一样令人惊讶。

这就是为什么 NP 中语言的补语通常在 NP 中并不明显——事实上，我们有术语“co-NP”（如“补语在 NP 中”）来指代像 !CLIQUE 这样的语言.

在复杂性理论中取得进展的一种常见方法是，在困难问题上我们没有取得进展，是表明一些特定的难以证明的结果会暗示一些令人惊讶的事情。证明 NP=co-NP 是这些证明的共同目标——例如，NP 和 co-NP 中的任何难题可能都不完整，因为如果它对两者都是完整的，因此两者都是相等，所以不知何故你有那些疯狂的一般图形证明。

这甚至可以概括——你可以开始谈论如果你的 NTM（或证书检查器）有一个像 CLIQUE 这样的 NP 完整语言的预言机会发生什么。显然 CLIQUE 和 !CLIQUE 都在 P^CLIQUE 中，但现在（可能）在 NP^CLIQUE 和 co-NP^CLIQUE 中有（可能）新语言，您可以继续前进，直到您拥有完整的复杂性类层次结构—— “多项式层次结构”。这种层次结构直观地永远持续下去，但很可能在某些时候崩溃甚至根本不存在（如果 P=NP）。

多项式层次结构使这种通用论证技术更加强大——表明某些结果会使多项式层次结构崩溃到第 2 或第 3 级会使该结果非常令人惊讶。即使显示它完全崩溃也会有些令人惊讶。

于 2016-01-16T02:18:06.413 回答