将NP中的2个问题结合成一个

Question

说我有一个确定性的图灵机，它解决了Oracle访问问题的决策问题，其中包含在 $ np $ 中的b，c。 可以在 $ np $ 中，使用Oracle访问权限才能解决oracle访问权限一个问题？

即，可以在 $ np $ 中，以某种方式组合成一个问题（因此显示s在$ p ^ {np} $ ）？

Answer 1

至少有两种方法可以做到。首先是采用 $ b $ 和 $ c $ 的脱节和，可以在例如，多种方式 $$ \ {0x：x \ in b \} \ cup \ {1y：y \在c \}。 $$ 第二个是使用NP-Complete Language $ L $ 作为Oracle。由于NP中的任何问题减少到多项式时间中的 $ L $ ，因此可以模拟 $ b $ - Oracle使用 $ l $ -oracle。