7
$\begingroup$

Is the class $\sf NP$ closed under complement or is it unknown? I have looked online, but I couldn't find anything.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 2
    $\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$ – David Richerby Apr 30 '14 at 17:02
  • $\begingroup$ Thanks for the correction @DavidRicherby. Replaced "Conversely" with "Also". $\endgroup$ – joebloggs Apr 30 '14 at 17:44
14
$\begingroup$

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

$\endgroup$
-2
$\begingroup$

"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

$\endgroup$
-3
$\begingroup$

It is unknown. A proof of the P vs. NP problem would give you an answer.

$\endgroup$
  • 4
    $\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$ – David Richerby Apr 30 '14 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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