Участник:Темирлан/Полиномиальная иерархия/Задачи/P^SAT=P^NP — различия между версиями
Темирлан (обсуждение | вклад) (Новая страница: «По определению <latex>P^{NP}</latex>») |
Темирлан (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | По определению <latex>P^{NP}</latex> | + | По определению: <latex>P^{NP}</latex> - все такие языки, для которых существует такой язык из <latex>NP</latex>, что язык становится разрешимым за полиномиальное время на машине Тьюринга с оракулом - этим NP-языком. Т.к. <latex>SAT \in NP \Rightarrow P^{SAT} \in P^{NP}</latex>. |
| + | Покажем обратное включение: <latex>SAT \in NPC \Rightarrow \forall L \in NP </latex> существует полиномиальная сводимость языка <latex>L</latex> к SAT. Пусть M - машина, распознающая язык <latex>L\in P^{L_1}</latex>, где <latex>L_1 \in NP</latex>. Машина M' будет работать следующим образом: работает аналогично M, но при каждом запросе к оракулу <latex>L_1</latex> M' будет вычислять полиномиальную сводимость к SAT и сведенный экземпляр запрашивать у оракула SAT. Заметим: запросы на принадлежность <latex>L_1</latex> происходили для слов полиномиальной длины от входа (т.к.число задействованных ячеек не больше общего времени работы - полинома от длины), и т.к. полиномы замкнуты относительно композиции, машина M' будет работать не более чем полином шагов. Оракул SAT для M' будет возвращать такие же ответы, что и оракул <latex>L_1</latex> для M. Значит, результат работы совпадает. Отсюда: <latex>L \in P^{SAT}</latex> | ||
| + | |||
| + | [[Категория:На проверку]] | ||
Версия 21:16, 3 апреля 2017
По определению: - все такие языки, для которых существует такой язык из , что язык становится разрешимым за полиномиальное время на машине Тьюринга с оракулом - этим NP-языком. Т.к. . Покажем обратное включение: существует полиномиальная сводимость языка к SAT. Пусть M - машина, распознающая язык , где . Машина M' будет работать следующим образом: работает аналогично M, но при каждом запросе к оракулу M' будет вычислять полиномиальную сводимость к SAT и сведенный экземпляр запрашивать у оракула SAT. Заметим: запросы на принадлежность происходили для слов полиномиальной длины от входа (т.к.число задействованных ячеек не больше общего времени работы - полинома от длины), и т.к. полиномы замкнуты относительно композиции, машина M' будет работать не более чем полином шагов. Оракул SAT для M' будет возвращать такие же ответы, что и оракул для M. Значит, результат работы совпадает. Отсюда: