0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – rus9384 Jul 13 '17 at 9:57
  • $\begingroup$ 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. $\endgroup$ – Covvar Jul 13 '17 at 10:00
  • $\begingroup$ so that leads me to the question, how do we simulate those $TM$s? $\endgroup$ – Covvar Jul 13 '17 at 10:01
  • $\begingroup$ But you only flipped a problem from $NP\cap coNP$. It can be done from definition. $\endgroup$ – rus9384 Jul 13 '17 at 10:01
  • 1
    $\begingroup$ 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. $\endgroup$ – rus9384 Jul 13 '17 at 10:09
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Covvar Jul 13 '17 at 10:39
  • $\begingroup$ 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. $\endgroup$ – Covvar Jul 13 '17 at 10:43
  • 1
    $\begingroup$ 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. $\endgroup$ – Ariel Jul 13 '17 at 10:46
  • $\begingroup$ 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. $\endgroup$ – Covvar Jul 13 '17 at 10:52
  • 1
    $\begingroup$ 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$. $\endgroup$ – Ariel Jul 13 '17 at 11:03

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.