# Combining 2 problems in NP into one

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

## 1 Answer

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.

• Thank you very much Yuval! – Ben May 28 '20 at 16:51
• Another downvoter not bothering to leave a comment... – Yuval Filmus May 31 '20 at 18:08