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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показано 14 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
Покажите, что <m>P \subseteq NP \cap coNP</m>.
 
Покажите, что <m>P \subseteq NP \cap coNP</m>.
  
−
[[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>
+

Текущая версия на 06:50, 4 мая 2023

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

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