# is the class NP closed under set difference?

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: • Do you know coNP?
– holf
Jun 5 at 18:11
• Note that if we knew of any difference between the P and NP row, we would know that $P \neq NP$.
– chi
Jun 11 at 17:34

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}$$.