Exactement l'un de NP et de co-NP peut-il être égal à P?

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

Non, car $\mathsf{P}$ est fermé pour compléter ce cant be, et nous savons même que $\mathsf{P}=\mathsf{NP} \implies \mathsf{NP}=\mathsf{co\text{-}NP}$ .

Supposons que $\mathsf{P}=\mathsf{NP}$ , et laissons $L \in \mathsf{co\text{-}NP}$ , donc $L^c \in \mathsf{NP}$ . Nous avons supposé $\mathsf{P}=\mathsf{NP}$ , et donc il existe un TM $M$ st $L(M)=L^c$ . Si nous prenons le "complément" de $M$ , c'est-à-dire une machine $M'$ qui est identique à $M$ sauf que ses états d'acceptation et de rejet sont inversés, nous obtenons que $L(M')=(L^c)^c=L$ , et ainsi $L$ est dans $\mathsf{NP}$ .

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

$\mathsf{P}$ est fermé sous complément (ie ¹); donc si (ou ) alors$\mathsf{P}=\mathsf{co\text{-}P}$$\mathsf{P}=\mathsf{co\text{-}NP}$$\mathsf{P}=\mathsf{NP}$$\mathsf{co\text{-}NP} = \mathsf{NP}$

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