В теории сложности вычислений , то полиномиальная иерархия (иногда называются полиномиальное время иерархия ) является иерархией из классов сложности , обобщающих классы NP и со-NP . [1] Каждый класс в иерархии содержится в PSPACE . Иерархия может быть определена с помощью машин-оракулов или чередующихся машин Тьюринга . Это ограниченный ресурсами аналог арифметической иерархии и аналитической иерархии из математической логики.. Объединение классов в иерархии обозначается PH .
Классы в иерархии имеют полные проблемы (относительно редукций за полиномиальное время ), которые спрашивают, верны ли количественные булевы формулы для формул с ограничениями на порядок кванторов. Известно, что равенство между классами на одном уровне или на последовательных уровнях иерархии будет означать «коллапс» иерархии на этот уровень.
Определения
Существует несколько эквивалентных определений классов полиномиальной иерархии.
Определение Oracle
Для определения полиномиальной иерархии оракулом определите
где P - множество задач принятия решений, решаемых за полиномиальное время . Тогда для i ≥ 0 определим
где - множество задач решения, решаемых за полиномиальное время машиной Тьюринга, дополненное оракулом для некоторой полной проблемы в классе A; классы а также определяются аналогично. Например,, а также - класс задач, решаемых за полиномиальное время с оракулом для некоторой NP-полной задачи. [2]
Определение количественных булевых формул
Для экзистенциального / универсального определения полиномиальной иерархии, пусть L будет языком (т.е. проблема решения , подмножество {0,1} * ), пусть p будет многочленом , и определим
где - это стандартное кодирование пары двоичных строк x и w как одной двоичной строки. L представляет собой набор упорядоченных пар строк, где первая строка x является членом, а вторая строка w - "короткая" () свидетель, показывающий, что x является членом. Другими словами,тогда и только тогда, когда существует короткий свидетель w такой, что. Аналогичным образом определим
Обратите внимание, что законы Де Моргана : а также , Где L с является дополнением L .
Пусть C - класс языков. Расширить эти операторы для работы со всеми классами языков по определению
Опять же, законы Де Моргана гласят: а также , где .
Классы NP и co-NP можно определить как, а также , где P - класс всех допустимо (полиномиально-временных) разрешимых языков. Полиномиальная иерархия может быть определена рекурсивно как
Обратите внимание, что , а также .
Это определение отражает тесную связь между иерархией полиномов и арифметической иерархией , где R и RE играют роли, аналогичные P и NP , соответственно. Аналитическая иерархия также определяется таким же образом , чтобы дать иерархию подмножеств действительных чисел.
Определение чередующихся машин Тьюринга
Переменный машин Тьюринга не является детерминированной машиной Тьюринга с не-конечными состояниями разбиваются на экзистенциальные и универсальные состояния. В конечном итоге он принимает текущую конфигурацию, если: он находится в экзистенциальном состоянии и может перейти в некоторую, в конечном итоге, принимающую конфигурацию; или он находится в универсальном состоянии, и каждый переход находится в некоторой, в конечном итоге, принимающей конфигурации; или он находится в принимающем состоянии. [3]
Мы определяем быть классом языков, принимаемых чередующейся машиной Тьюринга за полиномиальное время, так что начальное состояние является экзистенциальным состоянием, и каждый путь, по которому машина может проходить обмены между экзистенциальным и универсальным состояниями не более k - 1 раз. Мы определяеманалогично, за исключением того, что начальное состояние является универсальным. [4]
Если мы опустим требование не более k - 1 перестановок между экзистенциальным и универсальным состояниями, так что нам нужно только, чтобы наша чередующаяся машина Тьюринга работала за полиномиальное время, тогда у нас есть определение класса AP , которое равно PSPACE . [5]
Отношения между классами в полиномиальной иерархии
Объединение всех классов в полиномиальной иерархии - это класс сложности PH .
Под определениями подразумеваются отношения:
В отличие от арифметических и аналитических иерархий, чьи включения считаются правильными, остается открытым вопрос, являются ли какие-либо из этих включений правильными, хотя широко распространено мнение, что все они правильны. Если есть, или если есть , то иерархия схлопывается до уровня k : для всех, . [6] В частности, мы имеем следующие последствия, связанные с нерешенными проблемами:
Отношения с другими классами
Полиномиальная иерархия является аналогом (с гораздо меньшей сложностью) экспоненциальной иерархии и арифметической иерархии .
Известно, что PH содержится в PSPACE , но неизвестно, равны ли эти два класса. Одна полезная переформулировка этой проблемы состоит в том, что PH = PSPACE тогда и только тогда, когда логика второго порядка над конечными структурами не получает дополнительной мощности от добавления оператора транзитивного замыкания .
Если полиномиальная иерархия имеет какие-либо полные проблемы , то она имеет только конечное число различных уровней. Поскольку существуют проблемы с полным PSPACE , мы знаем, что если PSPACE = PH, то иерархия полиномов должна разрушиться, поскольку проблема с полным PSPACE будет-полная задача для некоторого k . [8]
Каждый класс в полиномиальной иерархии содержит -полные задачи (задачи, завершенные при полиномиальном времени много-однозначных редукций). Кроме того, каждый класс в полиномиальной иерархии замкнут относительно-редукции : означает, что для класса C в иерархии и языка, если , тогда также. Эти два факта вместе означают, что если это полная проблема для , тогда , а также . Например,. Другими словами, если язык определяется на основе некоторого оракула в С , то можно считать , что она определена на основе полной задачи для C . Таким образом, завершенные задачи действуют как «представители» того класса, для которого они завершены.
Теорема Сипсера – Лаутеманна утверждает, что класс BPP содержится на втором уровне полиномиальной иерархии.
Теорема Каннана утверждает, что для любого k ,не содержится в РАЗМЕРЕ (n k ).
Теорема Тоды утверждает, что иерархия полиномов содержится в P #P .
Проблемы
- Пример естественной проблемы в является минимизация цепи : дано число K и схема вычисления булевой функции F , определить, есть ли цепь с не более K ворот , который вычисляет ту же функцию п . Пусть C - множество всех логических схем. Язык
разрешима за полиномиальное время. Язык
- Полная проблема для это выполнимость для булевых формул количественно с к - 1 чередований кванторов (сокращенно QBF K или QSAT K ). Это версия проблемы логической выполнимости для. В этой задаче нам дана булева формула f с переменными, разбитыми на k множеств X 1 , ..., X k . Мы должны определить, правда ли, что
- В этом Сборнике можно найти список задач в стиле Гэри / Джонсона, которые, как известно, являются полными для второго и более высоких уровней полиномиальной иерархии .
Смотрите также
- EXPTIME
- Экспоненциальная иерархия
- Арифметическая иерархия
Рекомендации
- ^ Arora и Barak, 2009, pp.97
- ^ Полнота в иерархии полиномиального времени Компендиум, М. Шефер, К. Уманс
- ^ Arora и Barak, pp.99-100
- ^ Арора и Барак, стр 100
- ^ Арора и Барак, стр 100
- ↑ Арора и Барак, 2009, теорема 5.4.
- ^ Hemaspaandra, Lane (2018). «17.5 Классы сложности». В Розене, Кеннет Х. (ред.). Справочник по дискретной и комбинаторной математике . Дискретная математика и ее приложения (2-е изд.). CRC Press. С. 1308–1314. ISBN 9781351644051.
- ↑ Арора и Барак, 2009, Утверждение 5.5.
Общие ссылки
- Арора, Санджив; Варак, Вооз (2009). Теория сложности: современный подход . Издательство Кембриджского университета. ISBN 978-0-521-42426-4.
раздел 1.4, «Машины как струны и универсальная машина Тьюринга» и 1.7, «Доказательство теоремы 1.9».
- А. Р. Мейер и Л. Дж. Стокмейер . Проблема эквивалентности регулярных выражений с возведением в квадрат требует экспоненциального пространства. In Proceedings of the 13th IEEE Symposium on Switching and Automata Theory , pp. 125–129, 1972. Статья, в которой представлена полиномиальная иерархия.
- LJ Stockmeyer . Иерархия полиномиального времени . Теоретическая информатика , том 3, стр. 1–22, 1976.
- C. Papadimitriou . Вычислительная сложность. Addison-Wesley, 1994. Глава 17. Полиномиальная иерархия , стр. 409–438.
- Майкл Р. Гарей и Дэвид С. Джонсон (1979). Компьютеры и непоколебимость: руководство по теории NP-полноты . WH Freeman. ISBN 0-7167-1045-5. Раздел 7.2: Полиномиальная иерархия, стр. 161–167.