Kombinieren Sie 2 Probleme in NP in eins
-
29-09-2020 - |
Frage
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
das heißt, kann b und c irgendwie in ein Problem in $ NP $ (somit zeigen, dass S in ist$ P ^ {np} $ )?
Lösung
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