Is the class $\sf NP$ closed under complement or is it unknown? I have looked online, but I couldn't find anything.
$\begingroup$
$\endgroup$
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
2
The answer is "not known to science". It is known that P is closed under complement. So if P = NP then NP is closed under complement as well. Also, if NP is not closed under complement, then P != NP.
-
3$\begingroup$ The converse of "If P=NP, then NP is closed under complement" would be "If NP is closed under complement, then P=NP". However, this is not known to be true: it is possible that NP is closed under complement but is still different from P. $\endgroup$ Commented Apr 30, 2014 at 17:02
-
$\begingroup$ Thanks for the correction @DavidRicherby. Replaced "Conversely" with "Also". $\endgroup$ Commented Apr 30, 2014 at 17:44
$\begingroup$
$\endgroup$
First of all, the question you are asking is open, since an affirmative answer shows that $\sf NP = coNP$. In fact it is one of the most prominent open problems in computer science.
If $\sf P= NP$, then the class $\sf NP$ is closed under complement since $\sf P$ is. If on the other hand $\sf P \not = NP$ then we cannot say whether $\sf NP = coNP$ or not. Notice that $\sf NP = coNP$ implies that the polynomial hierarchy collapses to the first level. However this would not imply that $\sf P= NP$.
$\begingroup$
$\endgroup$
1
It is unknown. A proof of the P vs. NP problem would give you an answer.
-
6$\begingroup$ No it wouldn't. If P$\neq$NP (which is what most complexity theorists believe), then it's possible that either NP=coNP or NP$\neq$coNP. $\endgroup$ Commented Apr 30, 2014 at 17:14
$\begingroup$
$\endgroup$
2
"Every deterministic complexity class (DSPACE(f(n)), DTIME(f(n)) for all f(n)) is closed under complement, because one can simply add a last step to the algorithm which reverses the answer. This doesn't work for nondeterministic complexity classes, because if there exist both computation paths which accept and paths which reject, and all the paths reverse their answer, there will still be paths which accept and paths which reject — consequently, the machine accepts in both cases". Source
-
3$\begingroup$ This only shows that one way of proving closure under complementation doesn't work. Other ways might be possible – for example, NL is closed under complementation, and the same holds for many other nondeterministic space complexity classes. $\endgroup$ Commented Nov 16, 2018 at 3:46
-
1$\begingroup$ Also, we're looking for answers, not copy-pastes from Wikipedia. (But thanks for acknowledging your source.) $\endgroup$ Commented Nov 16, 2018 at 9:54