Combining 2 problems in NP into one
-
29-09-2020 - |
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}$)?
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