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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<latex> \begin{itemize} \item{Очевидно, что для любого языка, разрешимого за полиномиальное время, сущ…»)
 
 
Строка 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$. Поэтому $R\subseteq 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