# If we can simulate $NP$-machines why isn't it trivial that $NP=coNP$?

I'm looking at some proof that shows $NP^{NP\cap coNP} = NP$.

Let's consider the non-trivial direction. Consider $L\in NP^{NP\cap coNP}$. Then, there's an $A\in NP\cap coNP$ such that $L\in NP^A$.

Since $A\in NP\cap coNP$, there're two machines $M_A$ and $M_{\overline A}$ to decide $A$ and $\overline A$, respectively.

Also, there's a machine $M_L$ to decide $L$ which uses an oracle of $A$.

Let $M$ which acts in the following manner:

1. Act as $M_L$.
2. instead of querying the oracle:
3. simulate the query on $M_A$
4. simulate the query on $M_\overline A$
5. write on the result tape the proper result and proceed

I don't understand few things:

1. How do we simulate $M_A$ and $M_\overline A$ exactly?
2. If we can do the above then why both $M_A$ and $M_\overline A$ are needed? (just simulate one of them to infer if $x\in A$ or not)
3. Finally, as a consequence of #2, we could infer that $NP=coNP$

I'd be glad for clarifications since this questions bothers me a lot and clearly, I'm missing something crucial of how those machines are simulated.

• Here you only say that $NP\cap coNP$ is low for $NP$ which is known since it is low even for itself. Also, your p.3 is not consistent with previous paragraphs. Why did you conclude that it leads to $NP=coNP$? – rus9384 Jul 13 '17 at 9:57
• I am aware of the problem that we can't just take some $NP$ machine and flip it's accepting/rejecting states to get the corresponding $coNP$ machine, but if we could simulate it and look at the "final result" then we can obviously return the opposite of it - which is exactly the complement language. – Covvar Jul 13 '17 at 10:00
• so that leads me to the question, how do we simulate those $TM$s? – Covvar Jul 13 '17 at 10:01
• But you only flipped a problem from $NP\cap coNP$. It can be done from definition. – rus9384 Jul 13 '17 at 10:01
• Well, actually, either $M_A$ or $M_{\overline A}$ is true. First you simulate $M_A$ and if it's true, your $M_L$ machine chooses it. But if not, I think the case is that $NP$ machine can't make such conclusions immediately, unlike deterministic machine. – rus9384 Jul 13 '17 at 10:09

## 1 Answer

When we say "Simulate $M_A$ on the query string $s$", we simply mean execute $M_A(s)$. Note that you construct a non-deterministic machine for $L$, thus you are able to simulate other non-deterministic machines. If both $M_A(s)$ and $M_{\overline{A}}(s)$ output $0$, then stop and reject $x$ (the initial input). Only when one of the machines outputs $1$, you can be sure about whether or not $s\in A$, and can continue simulating the oracle machine for $L$.

Note that this newly constructed non-deterministic polynomial time machine, $M(x)$, may accept its input $x$ only in computations where for each query $s$ raised during the computation, either $M_A(s)$ or $M_{\overline{A}}(s)$ output 1. Using this observation, you can simply show that $M$ indeed decides $L$.

• I see. Our main problem is that some string could be invalid for both $A$ and $\overline A$ (i.e. $x$ doesn't describe a valid graph). – Covvar Jul 13 '17 at 10:39
• Putting it into practice, when reaching an accepting state of $M_A$ we writes "YES". Otherwise, we simulate $M_\overline A$ and writes "NO" if reaching an accepting state. – Covvar Jul 13 '17 at 10:43
• I'm not sure I understand. For all $s\in\Sigma^*$, it obviously holds that $s\in A \lor s\in \overline{A}$. The problem arises from the fact you have a non-deterministic machine for $A$, say $M_A$, which might not tell you the information you need to know in a single execution. If $M_A(s)=1$, you can be sure that $s\in A$ and you're fine, however if $M_A(s)=0$ you're stuck. Luckily, since $\mathsf{A\in NP\cap coNP}$, you can execute both $M_A(s),M_\overline{A}(s)$, and simply drop the computation (i.e. reject the input) when both output 0. – Ariel Jul 13 '17 at 10:46
• just interpreting what you're saying: it's possible that $M_A(s) = 0$ though $x\in A$ (since we're looking at some single branch reached a rejecting state). So from that point, we use $M_\overline A$ to check which case is it. – Covvar Jul 13 '17 at 10:52
• Yes, but executing $M_\overline{A}(s)$ might also not reveal the information you want, as it too can output $0$. If this is the case, reject $x$ (do not mix the input $x$ with the query string $s$). You can do this because you can rely on the existence of a computation where for each query $s$, either $M_A(s)$ or $M_\overline{A}(s)$ output $1$. – Ariel Jul 13 '17 at 11:03