Combinando 2 problemas no NP em um

Question

Diga que eu tenho uma máquina de Turing determinística que resolve o problema de decisão S com o acesso à Oracle a ambos os problemas B, C que estão em $ NP $ . Pode ser resolvido com o Access Oracle a apenas um problema na $ NP $ ?

isto é, pode b e c de alguma forma ser combinado em um problema em $ NP $ (Assim, a exibição S está em $ P ^ {np} $ )?

Answer 1

Há pelo menos duas maneiras de fazê-lo.O primeiro é tomar uma soma disjunta de $ B $ e $ c $ , que pode ser feito emMuitas maneiras, por exemplo $$ \ {0x: x \ in b \} \ copo \ {1y: y \ in c \}. $$ A segunda é usar uma linguagem NP-completa $ l $ como um Oracle.Como qualquer problema no NP reduz para $ l $ no tempo polinomial, você pode simular uma $ B $ -Oracle usando uma $ l $ -oracle.