2
$\begingroup$

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}$)?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you very much Yuval! $\endgroup$
    – Ben
    Commented May 28, 2020 at 16:51
  • $\begingroup$ Another downvoter not bothering to leave a comment... $\endgroup$ Commented May 31, 2020 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.