Участник:USSRocker/ex-p-in-np-and-conp — Бойко Дмитрий, 175 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
Строка 1: Строка 1:
 +
[[Category:На проверку]]
 +
[[User:USSRocker|Дмитрий Бойко, 175]]
 +
 
Покажите, что <m>P \subseteq NP \cap coNP</m>.
 
Покажите, что <m>P \subseteq NP \cap coNP</m>.
  
[[/Решение Кудрицкого К.В.]]
+
<latex>
 +
\begin{document}
 +
1. $P\subseteq NP$. Определение NP требует наличие возможности проверки
 +
решения задачи за полиномиальное время, а задачи из $P$ и так выдают
 +
верное решение за нужное время.
 +
 
 +
2. По определению $coNP=\{L|\overline{L}\in NP\}$, но найдутся и такие
 +
$\overline{L'}$, которые принадлежат $P$. Значит, $L'\in P$, учитывая
 +
замкнутость относительно дополнения $P$, вытекающую из замкнутости
 +
$DTIME$.  
  
[[Category:Нерешенные задачи]]
+
Всем этим и доказана задача.
<!--Вообще-то, решения уже есть-->
+
\end{document}
 +
<\latex>

Версия 16:12, 11 июня 2014

Дмитрий Бойко, 175

Покажите, что .