Peut exactement l'un des NP et co-NP égal à P?

Question

Peut-être que je manque quelque chose d'évident, mais peut-il que P = co-NP $ \ subsetneq $ NP ou vice versa? Mon sentiment est qu'il doit y avoir un théorème qui exclut cette possibilité.

Answer 1

Non, parce que $ \ mathsf {P} $ est fermé pour compléter ce ne peut pas être, et nous savons même que $ \ mathsf {P} = \ mathsf {NP} \ implique \ mathsf {NP} = \ mathsf {co \ texte {-}. NP} $

Supposons que $ \ mathsf {P} = \ mathsf {NP} $, et que $ L \ in \ mathsf {co \ texte {-} NP} $, donc $ L ^ c \ in \ mathsf { NP} $. Nous supposions $ \ mathsf {P} = \ {mathsf NP} $, et, par conséquent, il existe un TM M $ S.T. $ $ L (M) = L ^ c $. Si nous prenons le « complément » de $ M $, qui est une machine $ M '$, ce qui est identique à $ M $, sauf les accepter et rejeter les états sont inversés, nous obtenons que $ L (M) = (L ^ c ) ^ c = L $, et donc $ L $ est en $ \ mathsf {NP} $.

Cela montre que, sous l'hypothèse que $ \ mathsf {P} = \ mathsf {NP} $, nous obtenons $ (\ mathsf {P} =) \ mathsf {NP} = \ mathsf {co \ texte {- } NP} $ et donc $ \ mathsf {P} = \ {mathsf co \ texte {-.} NP} $

Answer 2

$ \ mathsf {P} $ est fermé en complément (à savoir $ \ mathsf {P} = \ {mathsf co \ texte {-} P} $ ¹); donc si $ \ mathsf {P} = \ mathsf {co \ texte {-} NP} $ (ou $ \ mathsf {P} = \ mathsf {NP} $) alors $ \ mathsf {co \ texte {-} NP} = \ {mathsf NP} $

---

1. Étant donné une langue $ L \ in \ mathsf {P} $, nous pouvons construire un TM déterministe » qui décide $ \ overline L $ en temps polynomial simplement en prenant le TM qui décide $ L $ et ...