Участник:Темирлан/Полиномиальная иерархия/Задачи/P^SAT=P^NP — различия между версиями
StasFomin (обсуждение | вклад) |
Темирлан (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| + | *[[Полиномиальная иерархия/Задачи/P^SAT=P^NP]] | ||
| + | |||
По определению: <latex>P^{NP}</latex> - все такие языки, для которых существует такой язык из <latex>NP</latex>, что язык становится разрешимым за полиномиальное время на машине Тьюринга с оракулом - этим NP-языком. Т.к. <latex>SAT \in NP \Rightarrow P^{SAT} \in 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> | Покажем обратное включение: <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> | ||
Версия 15:19, 16 апреля 2017
По определению: - все такие языки, для которых существует такой язык из , что язык становится разрешимым за полиномиальное время на машине Тьюринга с оракулом - этим NP-языком. Т.к. . Покажем обратное включение: существует полиномиальная сводимость языка к SAT. Пусть M - машина, распознающая язык , где . Машина M' будет работать следующим образом: работает аналогично M, но при каждом запросе к оракулу M' будет вычислять полиномиальную сводимость к SAT и сведенный экземпляр запрашивать у оракула SAT. Заметим: запросы на принадлежность происходили для слов полиномиальной длины от входа (т.к.число задействованных ячеек не больше общего времени работы - полинома от длины), и т.к. полиномы замкнуты относительно композиции, машина M' будет работать не более чем полином шагов. Оракул SAT для M' будет возвращать такие же ответы, что и оракул для M. Значит, результат работы совпадает. Отсюда:
StasFomin (обсуждение) 06:44, 6 апреля 2017 (UTC): Я настаиваю, чтобы были ссылки на решаемую задачу. Раньше я в ваши решения вставлял, теперь, чтобы запомнили, прошу сделать самим.