NP의 2 가지 문제를 하나로 결합합니다

Question

$ np $ 에있는 두 가지 문제 b, 두 문제 B에 대한 오라클 액세스와 함께 결정 문제를 해결하는 결정적 튜링 머신이 있다고 가정 해보십시오. $ NP $ 에서 문제에 대한 오라클 액세스로 해결할 수 있습니까?

즉, $ np $ 에서 $ p ^ {np} $ )?

Answer 1

적어도 두 가지 방법이 있습니다.첫 번째는 $ b $ 및 $ C $ 의 분리 된 합계를 취하는 것입니다.많은 방법으로, 예를 들어 $$ \ {0x : x \ \} \ 컵 \ {1Y : y \ in c \}. $$ 두 번째는 NP-Cleass $ l $ 을 Oracle으로 사용하는 것입니다.NP의 문제가 $ L $ 에서 다항식 시간으로 줄어들므로 $ B $ 을 시뮬레이트 할 수 있습니다.Oracle $ l $ -Oracle.