Участник:Темирлан/Полиномиальная иерархия/Задачи/P^SAT=P^NP — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Проблемы в решении]] на :Уже не исправить]])
 
(не показаны 2 промежуточные версии 2 участников)
Строка 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>
  
[[Категория:На проверку]]
+
 
 +
[[Участник:StasFomin|StasFomin]] ([[Обсуждение участника:StasFomin|обсуждение]]) 06:44, 6 апреля 2017 (UTC): Я настаиваю, чтобы были ссылки на решаемую задачу. Раньше я в ваши решения вставлял, теперь, чтобы запомнили, прошу сделать самим.
 +
 
 +
[[Категория:Уже не исправить]]

Текущая версия на 23:50, 20 мая 2020

По определению: - все такие языки, для которых существует такой язык из , что язык становится разрешимым за полиномиальное время на машине Тьюринга с оракулом - этим NP-языком. Т.к. . Покажем обратное включение: существует полиномиальная сводимость языка к SAT. Пусть M - машина, распознающая язык , где . Машина M' будет работать следующим образом: работает аналогично M, но при каждом запросе к оракулу M' будет вычислять полиномиальную сводимость к SAT и сведенный экземпляр запрашивать у оракула SAT. Заметим: запросы на принадлежность происходили для слов полиномиальной длины от входа (т.к.число задействованных ячеек не больше общего времени работы - полинома от длины), и т.к. полиномы замкнуты относительно композиции, машина M' будет работать не более чем полином шагов. Оракул SAT для M' будет возвращать такие же ответы, что и оракул для M. Значит, результат работы совпадает. Отсюда:


StasFomin (обсуждение) 06:44, 6 апреля 2017 (UTC): Я настаиваю, чтобы были ссылки на решаемую задачу. Раньше я в ваши решения вставлял, теперь, чтобы запомнили, прошу сделать самим.