1
$\begingroup$

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: enter image description here

$\endgroup$
2
  • $\begingroup$ Do you know coNP? $\endgroup$
    – holf
    Jun 5, 2023 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$
    – chi
    Jun 11, 2023 at 17:34

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ thanks! so is the table I added to the post correct? $\endgroup$
    – Skynet
    Jun 5, 2023 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.