Say I have a deterministic turing machine which solves decision problem S with oracle access to both problems B, C that are in $NP$. Can S be solved with oracle access to only one problem in $NP$?

That is, can B and C somehow be combined into one problem in $NP$ (thus showing S is in $P^{NP}$)?


There are at least two ways to do it. The first is to take a disjoint sum of $B$ and $C$, which can be done in many ways, for example $$ \{0x : x \in B\} \cup \{1y : y \in C\}. $$ The second is to use an NP-complete language $L$ as an oracle. Since any problem in NP reduces to $L$ in polynomial time, you can simulate a $B$-oracle using an $L$-oracle.

| cite | improve this answer | |
  • $\begingroup$ Thank you very much Yuval! $\endgroup$ – Ben May 28 at 16:51
  • $\begingroup$ Another downvoter not bothering to leave a comment... $\endgroup$ – Yuval Filmus May 31 at 18:08

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.