Vielleicht fehlt mir etwas Offensichtliches, aber kann es sein, dass P = co-NP NP oder umgekehrt? Mein Gefühl ist, dass es einen Satz geben muss, der diese Möglichkeit ausschließt.
quelle
Vielleicht fehlt mir etwas Offensichtliches, aber kann es sein, dass P = co-NP NP oder umgekehrt? Mein Gefühl ist, dass es einen Satz geben muss, der diese Möglichkeit ausschließt.
Nein, weil geschlossen ist, um dies nicht zu ergänzen, und wir sogar wissen, dass .
Nehmen wir an, dass und , also . Wir haben , und daher existiert ein TM st . Wenn wir das "Komplement" von , das heißt eine Maschine die mit M identisch ist, außer dass ihre Annahme- und Ablehnungszustände umgekehrt sind, erhalten wir und also ist in .
Dies zeigt , dass, unter der Annahme , dass , erhalten wir und somit .
wird unter Komplement geschlossen (dh ¹); Wenn also (oder ), dann ist