Просмотр исходного текста страницы Полиномиальная иерархия. Доказать, что если P=NP, то P=coNP/Решение Иноземцев

<latex>
\begin{itemize}
\item{Очевидно, что для любого языка, разрешимого за полиномиальное время, существует МТ, который разрешает его за недетерминированное полиномиальное время. 
Поэтому $P\subseteq NP$}
\item{Также очевидно, что для языка $L\in P$, $\bar{L}\in P$ (можно просто брать противоположный выход МТ, разрешающей язык $L$). Из предыдущего пункта следует, что $\bar{L}\in NP$. И, согласно определению $coNP$, $L\in coNP$. Поэтому $P\subseteq coNP$.

Теперь покажем, что если $P=NP$, $coNP\subseteq P$.

Пусть $L\in coNP$. Следовательно, $\bar{L}\in NP = P$. Т.к. P замкнуто относительно дополнения (показано выше), $L\in P$.

Получили $coNP\subseteq P$, если $P=NP$.

Получили, что $P=coNP$, если $P=NP$

[[Категория:Предложенные студентами задачи]]