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

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

Версия 09:44, 6 апреля 2017

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


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