1
$\begingroup$

Please correct my statement. Assuming $L\in NP$, and algorithm A can determine L in poly-time in a nondeterministic machine, we have algorithm $A'$ and the complement of $L$ -- $L'$. $x$ is the input of $A'$

A'(x)
{
   if(A(x) is true)
      return false
   else
      return true
}

In this code, it seems like $A'$ can also run in a nondeterministic machine in poly-time. Can I just say $co-NP=NP$??

Or my flaw is that the input $x\in L'$ but $x\notin L$?

Could you please give me a specific example??

$\endgroup$
  • $\begingroup$ Nobody knows if $NP$ is closed under compliment. But we do know that, if it is, then $P=NP$. $\endgroup$ – jmite Dec 3 '13 at 3:47
  • $\begingroup$ @jmite Why does NP being closed under complement imply that P=NP? For example, EXP is closed under complement but we know that P$\neq$EXP. $\endgroup$ – David Richerby Apr 30 '14 at 17:12
  • $\begingroup$ I think I probably had the implication backwards, I might have remembered wrong. $\endgroup$ – jmite May 1 '14 at 6:03