I know P is closed under all Boolean operations, but what about NP?
is NP closed under set difference and symmetric difference?
is this table accurate?
Edit:
updated table:
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Do you know coNP? $\endgroup$– holfJun 5 at 18:11
-
$\begingroup$ Note that if we knew of any difference between the P and NP row, we would know that $P \neq NP$. $\endgroup$– chiJun 11 at 17:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
It is unknown whether $\mathsf{NP}$ is closed under set-difference.
If $\mathsf{NP}$ were known to be closed under set-difference then we would know that $\mathsf{NP} = \textsf{co-NP}$. Indeed, for $L \in \textsf{co-NP}$, $L = \Sigma^* \setminus \overline{L}$ where $\overline{L} \in \textsf{NP}$ and hence $\textsf{co-NP} \subseteq \textsf{NP}$. Moreover, for $L \in \textsf{NP}$, $L = \Sigma^* \setminus \overline{L}$ where $\overline{L} \in \textsf{co-NP} \subseteq \textsf{NP}$ and hence $\textsf{NP} \subseteq \textsf{co-NP}$.
On the other hand, if $\mathsf{NP}$ was known not to be closed under set-difference then we would know that $\mathsf{P} \neq \mathsf{NP}$ (since $\mathsf{P}$ is closed under set difference).
Regarding the symmetric difference, notice that $\Sigma^* \, \Delta \, L = (\Sigma^* \setminus L) \cup (L \setminus \Sigma^*) = (\Sigma^* \setminus L) \cup \emptyset = \Sigma^* \setminus L = \overline{L}$.
-
$\begingroup$ thanks! so is the table I added to the post correct? $\endgroup$– SkynetJun 5 at 19:07