Combinando 2 problemas en NP en uno

Question

Digamos que tengo una máquina de Turing determinista que resuelve el problema de la decisión con el acceso a Oracle a ambos problemas B, C que están en $ np $ . ¿Se puede resolver con el acceso a Oracle a solo un problema uno en $ np $ ?

es decir, se puede combinar de alguna manera B y C en un solo problema en $ np $ (por lo que se muestra S en $ P ^ {np} $ )?

Answer 1

Hay al menos dos formas de hacerlo.El primero es tomar una suma de disjoint de $ b $ y $ C $ , que se puede hacer enMuchas maneras, por ejemplo, $$ \ {0x: x \ in b \} \ Cup \ {1Y: Y \ IN C \}. $$ El segundo es usar un lenguaje completo de NP $ l $ como un oráculo.Dado que cualquier problema en NP se reduce a $ l $ en el tiempo polinomial, puede simular un $ b $ -Oracle usando un $ l $ -oracle.