Полиномиальная иерархия. Доказать, что если P=NP, то P=coNP/Решение Иноземцев — различия между версиями
Материал из DISCOPAL
Igor (обсуждение | вклад) (Новая страница: «<latex> \begin{itemize} \item{Очевидно, что для любого языка, разрешимого за полиномиальное время, сущ…») |
Igor (обсуждение | вклад) |
||
Строка 3: | Строка 3: | ||
\item{Очевидно, что для любого языка, разрешимого за полиномиальное время, существует МТ, который разрешает его за недетерминированное полиномиальное время. | \item{Очевидно, что для любого языка, разрешимого за полиномиальное время, существует МТ, который разрешает его за недетерминированное полиномиальное время. | ||
Поэтому $P\subseteq NP$} | Поэтому $P\subseteq NP$} | ||
− | \item{Также очевидно, что для языка $L\in P$, $\bar{L}\in P$ (можно просто брать противоположный выход МТ, разрешающей язык $L$). Из предыдущего пункта следует, что $\bar{L}\in NP$. И, согласно определению $coNP$, $L\in coNP$. Поэтому $ | + | \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$. | Теперь покажем, что если $P=NP$, $coNP\subseteq P$. |
Текущая версия на 20:22, 10 декабря 2016