Czy otwarte pytanie NP = co-NP jest takie samo jak P = NP?

Zastanawiam się nad tym w oparciu o kilka miejsc online, w których można dzwonić $\sf NP=$ współ-$\sf NP$ główny otwarty problem ... ale nie mogę znaleźć żadnego wskazania, czy jest to to samo, co $\sf P=NP$ problem...

Nie. To kolejny otwarty problem i na pewno powiązany, ale inny. Klasa złożoności co-$\mathsf{NP}$ to zestaw języków, w których znajdują się uzupełnienia $\mathsf{NP}$; to znaczy zbiór problemów decyzyjnych, dla których odpowiedź „nie” ma deterministyczny weryfikator czasu wielomianowego. Na przykład pytanie „Czy ta formuła SAT jest niezadowalająca?” Jeśli odpowiedź brzmi „nie”, istnieje pewne zadowalające przypisanie zmiennych, które to potwierdza; to jest certyfikat weryfikatora.

To możliwe, że $\mathsf{P} \neq \mathsf{NP}$jeszcze $\mathsf{NP} =$współ-$\mathsf{NP}$.

Ale z drugiej strony, jeśli $\mathsf{P} = \mathsf{NP}$, następnie $\mathsf{NP} =$współ-$\mathsf{NP}$na pewno. Jest tak, ponieważ jeśli język jest w$\mathsf{P}$, to jest również jego uzupełnienie $\mathsf{P}$, więc jeśli $\mathsf{P} = \mathsf{NP}$, to odnosi się do każdego języka w $\mathsf{NP}$ także.

Jednym dobrym sposobem na odpowiedź na to pytanie jest użycie hierarchii wielomianowej (PH) (patrz również tutaj ). Hierarchia wielomianowa to hierarchia klas złożoności, która uogólnia klasy${\sf P}$, ${\sf NP}$ i ${\sf co-NP}$do wyroczni i używaj ich jako skali do pomiaru złożoności problemów.

Wiadomo, że jeśli ${\sf NP}={\sf co-NP}$ lub ${\sf P}={\sf NP}$następnie hierarchia wielomianowa upada na swój pierwszy poziom.