为什么两种NP完全语言的差异不属于NP？

Question

我在笔记中发现了一些我不太明白的内容，也许你可以帮忙。

设 $A$ = 独立集，$B$ = 派系。那么，我们显然有

• $A \in \mathsf{NPC}$ 和
• $B \in \mathsf{NP}$。

现在，声明是 $A \setminus B otin \mathsf{NP}$ 并具有以下解释。如果它在 $\mathsf{NP}$ 中，则 $\mathsf{NP} = \mathsf{NPC}$。

你能解释一下为什么这个论点是正确的吗？

Answer 1

这有点人为，但如果我们定义

$A = \{(G,k):G ext{ 有一组独立的大小 } k \}$

$B = \{(G,k):G ext{ 有一个规模为 } k \}$

那么 $A \setminus B$ 是 $\mathsf{coNP}$-困难的，因为我们可以将 $\overline{B}$ 简化为它：给定图 $G$ 和数字 $k$，我们可以通过将 $k$ 个孤立顶点添加到 $G$ 来形成 $G'$，然后 $(G',k) \in A\setminus B$ iff $(G ,k) \in \overline{B}$。

我声称

$A \setminus B \in \mathsf{NP} \Leftrightarrow \mathsf{NP}=\mathsf{coNP}$

$(\右箭头)$:如果 $\mathsf{coNP}$-hard 语言位于 $\mathsf{NP}$ 中，则 $\mathsf{NP}=\mathsf{coNP}$。

$(\向左箭头)$:如果 $\mathsf{NP}=\mathsf{coNP}$ 则 $A \setminus B \in \mathsf{NP}$ 后面是 $\mathsf{NP}$ 的闭包性质。

由于研究人员认为 $\mathsf{NP} eq \mathsf{coNP}$ （这是 $\mathsf{P} eq \mathsf{NP}$ 的更强版本），因此押注 $A \ setminus B otin \mathsf{NP}$。目前我们还没有证据。

Answer 2

两种 $\mathsf{NP}$ 语言之间的区别是 不必要 在$\mathsf{NP}$中。（可能是，但也可能不是。）

考虑 $A=\{0,1\}^*$ 和 $B$ 任何 $\mathsf{NP}$ 完整语言（例如 3SAT）。那么 $A \setminus B = \overline{B}$ 就是 $B$ 的补集。由于$B$ 是$\mathsf{NP}$ 完备的，根据定义$\overline{B}$ 是$\mathsf{coNP}$ 完备的。现在，如果任何 $\mathsf{coNP}$ 完整语言在 $\mathsf{NP}$ 中，则 $\mathsf{NP}=\mathsf{coNP}$ 成立。这将是一个非常令人惊讶的结果。

总结一下：大多数研究人员相信 $\mathsf{NP} e \mathsf{coNP}$ （就像他们相信 $\mathsf{P} e \mathsf{NP}$ 一样）；如果我们假设$\mathsf{NP} e \mathsf{coNP}$，那么在\mathsf{NP}$中存在语言$A,B \使得$A\setminus B otin \mathsf{ NP}$。

换句话说，在合理的假设下，两种 $\mathsf{NP}$ 语言之间的差异不一定在 $\mathsf{NP}$ 中。