# Why isn't coNP = NP? [duplicate]

I am having trouble understanding the class $coNP$. We defined

$$coNP = \left\{ \overline{A} : A \in NP \right\}$$

As far as I know, a language $A$ is in $NP$ if, and only if, a non-deterministic turing machine $M$ exists, which outputs $1$ if $w \in A$ and $0$ if $w \notin A$. But if this is true, then a turing machine $M'$ must exist which simulates $M$ and inverts the output:

$$M' = \begin{cases}0 \text{ if } M = 1\\1 \text{ if } M = 0\end{cases}$$

Therefore, $w \in A \implies w \notin L(M')$ and $w \notin A \implies w \in L(M')$, meaning that $L(M') = \overline{L(M)}$.

As $M'$ works in non-deterministic polynomial time, $L(M') \in NP$, and as $L(M') = \overline{L(M)}$, $\overline{L(M)} \in NP$, but $\overline{L(M)} \in coNP$ as well. As this holds true for all languages in $NP$, why isn't $coNP = NP$?

• take a problem from NP and check your arguments. – miracle173 Jun 5 '17 at 11:15
• @miracle173 Let's look at $CLIQUE$. $\overline{CLIQUE}$ is the set of all tuples $(G,n)$ for which no clique exists within $G$ with at least $n$ nodes. $M$ exists and outputs $1$ if such a clique exists, $0$ otherwise. Let $M'$ be a non-deterministic turing machine which outputs $0$ if such a clique exists, $1$ otherwise. $M'$ works in polynomial time and decides the language $\overline{CLIQUE}$, so $\overline{CLIQUE} \in NP$, right? – just.kidding Jun 5 '17 at 11:27
• You have to be more careful with your use of the definition of NP. – Raphael Jun 5 '17 at 14:45
• sorry, I was offline. Can you state this NP problem (the clique problem)? Can you describe the nondeterministic algorithm that solves this NP problem? – miracle173 Jun 5 '17 at 18:58

• Oh, so polynomial time only corresponds to the output of YES? If $w \notin A$, then $M$ can take exponential time even though $A \in NP$? – just.kidding Jun 5 '17 at 13:43