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

Материал из DISCOPAL
< Участник:Темирлан
Версия от 23:50, 20 мая 2020; StasFomin (обсуждение | вклад) (Массовая правка: замена :Проблемы в решении]] на :Уже не исправить]])

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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


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