Kombinieren Sie 2 Probleme in NP in eins

Question

sagen, ich habe eine deterministische Turniermaschine, die das Entscheidungsproblem S mit Oracle-Zugriff auf beide Probleme B, C, die in $ NP $ sind, löst. Kann s mit Oracle-Zugriff auf one problem in $ np $ gelöst werden?

das heißt, kann b und c irgendwie in ein Problem in $ NP $ (somit zeigen, dass S in ist$ P ^ {np} $ )?

Answer 1

Es gibt mindestens zwei Möglichkeiten, es zu tun.Die erste ist, eine disjunkte Summe von $ B $ und $ C $ , die in erfolgen kannZum Beispiel viele Wege $$ \ {0x: x \ in b \ \ \ cup \ {1Y: y \ in c \}. $$ Die zweite ist, eine NP-Complete-Sprache $ L $ als Oracle zu verwenden.Da jedes Problem in NP auf $ L $ in der Polynomzeit reduziert, können Sie einen $ B $ simulieren - -Oracle mit einem $ L $ -oracle.