Dapatkah tepatnya satu NP dan co-NP sama dengan P?

Mungkin saya kehilangan sesuatu yang jelas, tetapi mungkinkah itu P = co-NP $\subsetneq$NP atau sebaliknya? Perasaan saya adalah bahwa harus ada beberapa teorema yang mengesampingkan kemungkinan ini.

Tidak karena $\mathsf{P}$ditutup untuk melengkapi cant ini, dan kita bahkan tahu bahwa .$\mathsf{P}=\mathsf{NP} \implies \mathsf{NP}=\mathsf{co\text{-}NP}$

Mari kita asumsikan bahwa , dan biarkan , dengan demikian . Kami mengasumsikan , dan karenanya ada TM st . Jika kita mengambil "komplemen" dari , itu adalah mesin yang identik dengan kecuali keadaan terima dan tolaknya terbalik, kita mendapatkan bahwa , dan jadi ada di .$\mathsf{P}=\mathsf{NP}$$L \in \mathsf{co\text{-}NP}$$L^c \in \mathsf{NP}$$\mathsf{P}=\mathsf{NP}$$M$$L(M)=L^c$$M$$M'$$M$$L(M')=(L^c)^c=L$$L$$\mathsf{NP}$

Ini menunjukkan bahwa, dengan asumsi itu $\mathsf{P}=\mathsf{NP}$, kita mendapatkan $(\mathsf{P}=)\mathsf{NP}=\mathsf{co\text{-}NP}$ dan dengan demikian $\mathsf{P}=\mathsf{co\text{-}NP}$.

$\mathsf{P}$ ditutup di bawah komplemen (mis $\mathsf{P}=\mathsf{co\text{-}P}$¹); jadi jika$\mathsf{P}=\mathsf{co\text{-}NP}$ (atau $\mathsf{P}=\mathsf{NP}$) kemudian $\mathsf{co\text{-}NP} = \mathsf{NP}$

1. Diberi bahasa $L \in \mathsf{P}$, kita dapat membangun TM deterministik yang memutuskan $\overline L$ dalam waktu polinomial hanya dengan mengambil TM yang memutuskan $L$ dan ...