Puede exactamente uno de NP y co-NP ser igual a P?

Question

Tal vez me estoy perdiendo algo obvio, pero puede ser que P = co-NP $ \ $ subsetneq NP o viceversa? Mi sensación es que tiene que haber algún teorema que descarta esta posibilidad.

Answer 1

No, porque $ \ mathsf {P} $ está cerrado para complementar esto no puede ser, y que incluso sabe que $ \ mathsf {P} = \ mathsf {NP} \ implica \ mathsf {NP} = \ mathsf {co \ text {-}. NP} $

Supongamos que $ \ mathsf {P} = \ mathsf {NP} $, y dejó $ L \ en \ mathsf {co \ text {-} NP} $, por lo tanto $ L ^ c \ in \ mathsf { NP} $. Asumimos $ \ mathsf {P} = \ mathsf {NP} $, y por lo tanto existe una TM $ M $ S.T. $ L (M) = L ^ c $. Si tomamos el "complemento" de $ M $, que es una máquina $ M '$ que es idéntica a $ M $, excepto sus aceptar y rechazar los estados se invierten, tenemos que $ L (M') = (L ^ c ) ^ c = L $, y por lo tanto $ L $ es de $ \ mathsf {NP} $.

Esto muestra que, bajo el supuesto de que $ \ mathsf {P} = \ mathsf {NP} $, obtenemos $ (\ mathsf {P} =) \ mathsf {NP} = \ mathsf {co \ text {- NP}} $ y por lo tanto $ \ mathsf {P} = \ {mathsf co \ text {-.} NP} $

Answer 2

$ \ mathsf {P} $ es cerrado bajo complemento (es decir, $ \ mathsf {P} = \ mathsf {co \ text {-} P} $ ¹); por lo que si $ \ mathsf {P} = \ mathsf {co \ text {-} NP} $ (o $ \ mathsf {P} = \ mathsf {NP} $), entonces $ \ mathsf {co \ text {-} NP} = \ mathsf {NP} $

---

1. Dado un lenguaje L $ \ en \ mathsf {P} $, podemos construir una MT determinista' que decide $ \ overline L $ en tiempo polinómico simplemente tomando la TM que decide $ L $ y ...