Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-p-in-np-and-conp — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
Larisa (обсуждение | вклад) |
||
| Строка 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> | ||
Версия 22:19, 14 декабря 2014
Покажите, что .