Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/strong-nmt-good-characterization — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «Пусть есть язык ''L'', для которого * есть некая МТ ''M'', возвращает «0», «1», «?». * для любого <m…») |
StasFomin (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Покажите, что <m>L \in NP \cap \overline{NP}</m> | Покажите, что <m>L \in NP \cap \overline{NP}</m> | ||
| − | [[Категория: | + | [[Категория:Решенные задачи]] |
Версия 01:49, 15 апреля 2021
Пусть есть язык L, для которого
- есть некая МТ M, возвращает «0», «1», «?».
- для любого , все пути вычисления M(x) за полиномиальное время приводят к ответам «1» или «?», при том есть хотя бы один путь к «1».
- для любого , все пути вычисления M(x) за полиномиальное время приводят к ответам «0» или «?», при том есть хотя бы один путь к «0».
Покажите, что