Question

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

Was it helpful?

Solution

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top