Combinazione di 2 problemi in NP in uno

Question

Dì che ho una macchina di tentazione deterministica che risolve il problema decisionale s con accesso a oracle a entrambi i problemi B, c che sono in $ NP $ . Può essere risolto con accesso oracle a solo one problema in $ np $ ?

cioè, può B e C in qualche modo essere combinato in un unico problema in $ NP $ (mostrando così S è in $ P ^ {np} $ )?

Answer 1

Ci sono almeno due modi per farlo.Il primo è quello di prendere una somma disgiunta di $ B $ e $ c $ , che può essere fatto inmolti modi, per esempio $$ \ {0x: x \ in b \} \ cup \ {1y: y \ in c \}. $$ Il secondo è utilizzare una lingua completa di NP $ l $ come oracolo.Poiché qualsiasi problema in NP si riduce a $ L $ In tempo polinomiale, è possibile simulare una classe $ B $ -Oracle utilizzando una classe $ L $ -oracle.