Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-p-in-np-and-conp — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
Покажите, что <m>P \subseteq NP \cap coNP</m>.
 
Покажите, что <m>P \subseteq NP \cap coNP</m>.
  
−
[[Category:На проверку]]
+
[[Category:Решенные задачи]]
−
 
+
<!--Вообще-то, решения уже есть-->
−
<latex>
+
−
1. $P \subseteq NP$
+
−
\\$L \in P$, если существует детерминированная МТ, которая распознает L за время, ограниченное полиномом.
+
−
\\$L \in NP$, если существует недетерминированная МТ, которая распознает L за время ограниченное полиномом.
+
−
Так как ДМТ является частным случаем НМТ, то P \subseteq NP.
+
−
\\2. $P = coP \subseteq coNP => P \subseteq coNP.$
+
−
\\Докажем, что P = coP
+
−
\\$L \in P$ => существует МТ Т, которая для любого слово за полиномиальное время выдает ответ 1, если слово $\in L$, и 0, в обратном случае. Построим МТ Т', которая выдает ответ 1, если Т выдает 0, и 0, если Т выдает 1. Тогда Т', которая тоже работает за полиномиальное время, распознает \overline L. => \overline L \in P.
+
−
\\$P \subseteq NP, P \subseteq coNP => P \subseteq NP \cap coNP$
+
−
</latex>
+

Версия 02:12, 26 декабря 2014

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

Источник — «https://discopal.ispras.ru/index.php?title=Полиномиальные_сводимости_и_NP-полные_задачи._Классы_NP,_coNP,_NPC/Задачи/ex-p-in-np-and-conp&oldid=3515»