Полиномиальная иерархия - Polynomial hierarchy

В теории сложности вычислений , то полиномиальная иерархия (иногда называются полиномиальное время иерархия ) является иерархией из классов сложности , обобщающих классы NP и со-NP . Каждый класс в иерархии содержится в PSPACE . Иерархия может быть определена с помощью машин-оракулов или чередующихся машин Тьюринга . Это ограниченный ресурсами аналог арифметической иерархии и аналитической иерархии из математической логики . Объединение классов в иерархии обозначается PH .

Классы в иерархии имеют полные проблемы (относительно полиномиальных сокращений ), которые спрашивают, верны ли количественные булевы формулы для формул с ограничениями на порядок кванторов. Известно, что равенство между классами на одном уровне или на последовательных уровнях иерархии будет означать «коллапс» иерархии на этот уровень.

Определения

Существует несколько эквивалентных определений классов полиномиальной иерархии.

Определение Oracle

Для определения полиномиальной иерархии оракулом определите

{\ displaystyle \ Delta _ {0} ^ {\ mathsf {P}}: = \ Sigma _ {0} ^ {\ mathsf {P}}: = \ Pi _ {0} ^ {\ mathsf {P}}: = {\ mathsf {P}},}

где P - множество задач принятия решений, решаемых за полиномиальное время . Тогда для i ≥ 0 определим

{\ Displaystyle \ Delta _ {я + 1} ^ {\ mathsf {P}}: = {\ mathsf {P}} ^ {\ Sigma _ {я} ^ {\ mathsf {P}}}}

{\ Displaystyle \ Sigma _ {я + 1} ^ {\ mathsf {P}}: = {\ mathsf {NP}} ^ {\ Sigma _ {я} ^ {\ mathsf {P}}}}

{\ Displaystyle \ Pi _ {я + 1} ^ {\ mathsf {P}}: = {\ mathsf {coNP}} ^ {\ Sigma _ {i} ^ {\ mathsf {P}}}}

где - множество задач решения, решаемых за полиномиальное время машиной Тьюринга, дополненной оракулом для некоторой полной проблемы в классе A; классы и определяются аналогично. Например, и - класс задач, решаемых за полиномиальное время с помощью оракула для некоторой NP-полной задачи. ${\ Displaystyle {\ mathsf {P}} ^ {\ rm {A}}}$ ${\ displaystyle {\ mathsf {NP}} ^ {\ rm {A}}}$ ${\ Displaystyle {\ mathsf {coNP}} ^ {\ rm {A}}}$ ${\ Displaystyle \ Sigma _ {1} ^ {\ mathsf {P}} = {\ mathsf {NP}}, \ Pi _ {1} ^ {\ mathsf {P}} = {\ mathsf {coNP}}}$ ${\ Displaystyle \ Delta _ {2} ^ {\ mathsf {P}} = {\ mathsf {P ^ {NP}}}}$

Определение количественных булевых формул

Для экзистенциального / универсального определения полиномиальной иерархии, пусть $L$ будет языком (т.е. проблема решения , подмножество {0,1} ^* ), пусть $p$ будет многочленом , и определим

{\ Displaystyle \ существует ^ {п} L: = \ влево \ {х \ в \ {0,1 \} ^ {*} \ \ влево | \ \ влево (\ существует ш \ в \ {0,1 \} ^ {\ leq p (| x |)} \ right) \ langle x, w \ rangle \ in L \ right. \ right \},}

где - некоторая стандартная кодировка пары двоичных строк x и w как единой двоичной строки. L представляет собой набор упорядоченных пар строк, где первая строка x является членом , а вторая строка w - свидетель "short" ( ), свидетельствующий, что x является членом . Другими словами, если и только если существует короткий свидетель w такой, что . Аналогичным образом определим ${\ displaystyle \ langle x, w \ rangle \ in \ {0,1 \} ^ {*}}$ ${\ Displaystyle \ существует ^ {p} L}$ ${\ Displaystyle | вес | \ Leq р (| х |)}$ ${\ Displaystyle \ существует ^ {p} L}$ ${\ Displaystyle х \ в \ существует ^ {р} L}$ ${\ displaystyle \ langle x, w \ rangle \ in L}$

{\ Displaystyle \ forall ^ {p} L: = \ left \ {x \ in \ {0,1 \} ^ {*} \ left | \ \ left (\ forall w \ in \ {0,1 \} ^ {\ leq p (| x |)} \ right) \ langle x, w \ rangle \ in L \ right. \ right \}}

Обратите внимание , что законы Де Моргана имеют место и , где L ^с является дополнением L . ${\ Displaystyle \ влево (\ существует ^ {p} L \ right) ^ {\ rm {c}} = \ forall ^ {p} L ^ {\ rm {c}}}$ ${\ displaystyle \ left (\ forall ^ {p} L \ right) ^ {\ rm {c}} = \ exists ^ {p} L ^ {\ rm {c}}}$

Пусть C - класс языков. Расширить эти операторы для работы со всеми классами языков по определению

{\ displaystyle \ exists ^ {\ mathsf {P}} {\ mathcal {C}}: = \ left \ {\ exists ^ {p} L \ | \ p {\ text {- многочлен, а}} L \ in {\ mathcal {C}} \ right \}}

{\ displaystyle \ forall ^ {\ mathsf {P}} {\ mathcal {C}}: = \ left \ {\ forall ^ {p} L \ | \ p {\ text {- многочлен, а}} L \ in {\ mathcal {C}} \ right \}}

Опять же, действуют законы Де Моргана: и , где . ${\ displaystyle {\ mathsf {co}} \ exists ^ {\ mathsf {P}} {\ mathcal {C}} = \ forall ^ {\ mathsf {P}} {\ mathsf {co}} {\ mathcal {C }}}$ ${\ displaystyle {\ mathsf {co}} \ forall ^ {\ mathsf {P}} {\ mathcal {C}} = \ exists ^ {\ mathsf {P}} {\ mathsf {co}} {\ mathcal {C }}}$ ${\ Displaystyle {\ mathsf {co}} {\ mathcal {C}} = \ left \ {L ^ {c} | L \ in {\ mathcal {C}} \ right \}}$

Классы NP и co-NP можно определить как , и , где P - класс всех допустимо (полиномиально-временных) разрешимых языков. Полиномиальная иерархия может быть определена рекурсивно как ${\ Displaystyle {\ mathsf {NP}} = \ существует ^ {\ mathsf {P}} {\ mathsf {P}}}$ ${\ Displaystyle {\ mathsf {coNP}} = \ forall ^ {\ mathsf {P}} {\ mathsf {P}}}$

{\ displaystyle \ Sigma _ {0} ^ {\ mathsf {P}}: = \ Pi _ {0} ^ {\ mathsf {P}}: = {\ mathsf {P}}}

{\ Displaystyle \ Sigma _ {к + 1} ^ {\ mathsf {P}}: = \ существует ^ {\ mathsf {P}} \ Pi _ {k} ^ {\ mathsf {P}}}

{\ Displaystyle \ Pi _ {к + 1} ^ {\ mathsf {P}}: = \ forall ^ {\ mathsf {P}} \ Sigma _ {k} ^ {\ mathsf {P}}}

Обратите внимание, что , и . ${\ Displaystyle {\ mathsf {NP}} = \ Sigma _ {1} ^ {\ mathsf {P}}}$ ${\ Displaystyle {\ mathsf {coNP}} = \ Pi _ {1} ^ {\ mathsf {P}}}$

Это определение отражает тесную связь между иерархией полиномов и арифметической иерархией , где R и RE играют роли, аналогичные P и NP , соответственно. Аналитическая иерархия также определяется таким же образом , чтобы дать иерархию подмножеств действительных чисел.

Определение чередующихся машин Тьюринга

Переменный машин Тьюринга не является детерминированной машиной Тьюринга с не-конечными состояниями разбиваются на экзистенциальные и универсальные состояния. В конечном итоге он принимает текущую конфигурацию, если: он находится в экзистенциальном состоянии и может перейти в некоторую, в конечном итоге, принимающую конфигурацию; или он находится в универсальном состоянии, и каждый переход находится в некоторой, в конечном итоге, принимающей конфигурации; или он находится в принимающем состоянии.

Мы определяем как класс языков, принимаемых чередующейся машиной Тьюринга за полиномиальное время, так что начальное состояние является экзистенциальным состоянием, и каждый путь, по которому машина может менять местами не более k - 1 раз между экзистенциальным и универсальным состояниями. Мы определяем аналогично, за исключением того, что начальное состояние является универсальным. ${\ displaystyle \ Sigma _ {k} ^ {\ mathsf {P}}}$ ${\ displaystyle \ Pi _ {k} ^ {\ mathsf {P}}}$

Если мы опустим требование не более k - 1 перестановок между экзистенциальным и универсальным состояниями, так что нам нужно только, чтобы наша чередующаяся машина Тьюринга работала за полиномиальное время, тогда у нас есть определение класса AP , которое равно PSPACE .

Отношения между классами в полиномиальной иерархии

Коммутативная диаграмма, эквивалентная иерархии полиномиального времени. Стрелки обозначают включение.

Объединение всех классов в полиномиальной иерархии - это класс сложности PH .

Под определениями подразумеваются отношения:

{\ Displaystyle \ Sigma _ {я} ^ {\ mathsf {P}} \ substeq \ Delta _ {я + 1} ^ {\ mathsf {P}} \ substeq \ Sigma _ {я + 1} ^ {\ mathsf { П}}}

{\ Displaystyle \ Pi _ {я} ^ {\ mathsf {P}} \ substeq \ Delta _ {i + 1} ^ {\ mathsf {P}} \ substeq \ Pi _ {я + 1} ^ {\ mathsf { П}}}

{\ Displaystyle \ Sigma _ {я} ^ {\ mathsf {P}} = {\ mathsf {co}} \ Pi _ {i} ^ {\ mathsf {P}}}

В отличие от арифметических и аналитических иерархий, чьи включения считаются правильными, остается открытым вопрос, являются ли какие-либо из этих включений правильными, хотя широко распространено мнение, что все они правильны. Если какой - либо , или если какой - либо , то иерархия разрушается до уровня А : для всех , . В частности, мы имеем следующие последствия, связанные с нерешенными проблемами: ${\ Displaystyle \ Sigma _ {k} ^ {\ mathsf {P}} = \ Sigma _ {k + 1} ^ {\ mathsf {P}}}$ ${\ Displaystyle \ Sigma _ {k} ^ {\ mathsf {P}} = \ Pi _ {k} ^ {\ mathsf {P}}}$ ${\ displaystyle i> k}$ ${\ Displaystyle \ Sigma _ {я} ^ {\ mathsf {P}} = \ Sigma _ {k} ^ {\ mathsf {P}}}$

P = NP тогда и только тогда, когда P = PH .
Если NP = co-NP, то NP = PH . ( co-NP есть .) ${\ displaystyle \ Pi _ {1} ^ {\ mathsf {P}}}$

Случай , в котором NP = PH также называют как коллапс от PH до второго уровня . Случай Р = NP соответствует распаду PH до P .

Нерешенная проблема в информатике :

${\ Displaystyle {\ mathsf {P}} {\ overset {?} {=}} {\ mathsf {NP}}}$

(больше нерешенных проблем в информатике)

Вопрос обрушения первого уровня обычно считается чрезвычайно трудным. Большинство исследователей не верят в коллапс даже до второго уровня.

Отношения с другими классами

Нерешенная проблема в информатике :

${\ displaystyle {\ mathsf {PH}} {\ overset {?} {=}} {\ mathsf {PSPACE}}}$

(больше нерешенных проблем в информатике)

Полиномиальная иерархия является аналогом (с гораздо меньшей сложностью) экспоненциальной иерархии и арифметической иерархии .

Известно, что PH содержится в PSPACE , но неизвестно, равны ли эти два класса. Одна полезная переформулировка этой проблемы состоит в том, что PH = PSPACE тогда и только тогда, когда логика второго порядка над конечными структурами не получает дополнительной мощности от добавления оператора транзитивного замыкания .

Если полиномиальная иерархия имеет какие-либо полные проблемы , то она имеет только конечное число различных уровней. Поскольку существуют PSPACE-полные проблемы, мы знаем, что если PSPACE = PH, тогда полиномиальная иерархия должна разрушиться, поскольку PSPACE-полная проблема будет -полной проблемой для некоторого k . ${\ displaystyle \ Sigma _ {k} ^ {\ mathsf {P}}}$

Каждый класс в полиномиальной иерархии содержит -полные задачи (задачи, завершенные при полиномиальном времени много-однозначных редукций). Более того, каждый класс в полиномиальной иерархии замкнут относительно -редукции : это означает, что для класса C в иерархии и языка , если , то тоже. Эти два факта вместе означают, что if является полной проблемой для , then и . Так , например, . Другими словами, если язык определяется на основе некоторого оракула в С , то можно считать , что она определена на основе полной задачи для C . Таким образом, завершенные задачи действуют как «представители» того класса, для которого они завершены. ${\ displaystyle \ leq _ {\ rm {m}} ^ {\ mathsf {P}}}$ ${\ displaystyle \ leq _ {\ rm {m}} ^ {\ mathsf {P}}}$ ${\ displaystyle L \ in {\ mathcal {C}}}$ ${\ Displaystyle А \ leq _ {\ rm {m}} ^ {\ mathsf {P}} L}$ ${\ displaystyle A \ in {\ mathcal {C}}}$ ${\ displaystyle K_ {i}}$ ${\ Displaystyle \ Sigma _ {я} ^ {\ mathsf {P}}}$ ${\ Displaystyle \ Sigma _ {я + 1} ^ {\ mathsf {P}} = {\ mathsf {NP}} ^ {K_ {я}}}$ ${\ Displaystyle \ Pi _ {я + 1} ^ {\ mathsf {P}} = {\ mathsf {coNP}} ^ {K_ {i}}}$ ${\ Displaystyle \ Sigma _ {2} ^ {\ mathsf {P}} = {\ mathsf {NP}} ^ {\ mathsf {SAT}}}$

Теорема Сипсера – Лаутеманна утверждает, что класс BPP содержится на втором уровне полиномиальной иерархии.

Теорема Kannan в том , что для любого к , не содержится в SIZE (п ^к ). ${\ displaystyle \ Sigma _ {2}}$

Теорема Тоды утверждает, что иерархия полиномов содержится в P ^#P .

Проблемы

Примером естественной задачи является минимизация цепи : дано число K и схема вычисления булевой функции F , определить, есть ли цепь с не более K ворот , которая вычисляет ту же функцию п . Пусть C - множество всех логических схем. Язык ${\ Displaystyle \ Sigma _ {2} ^ {\ mathsf {P}}}$
${\ Displaystyle L = \ left \ {\ langle A, K, B, x \ rangle \ in {\ mathcal {C}} \ times \ mathbb {N} \ times {\ mathcal {C}} \ times \ {0 , 1 \} ^ {*} \ left | B {\ text {имеет не более}} k {\ text {gates, и}} A (x) = B (x) \ right. \ Right \}}$

разрешима за полиномиальное время. Язык

${\ displaystyle {\ mathit {CM}} = \ left \ {\ langle A, k \ rangle \ in {\ mathcal {C}} \ times \ mathbb {N} \ left | {\ begin {matrix} {\ text {существует схема}} B {\ text {не более}} k {\ text {gates}} \\ {\ text {такая, что}} A {\ text {и}} B {\ text {вычисляет та же функция}} \ end {matrix}} \ right. \ right \}}$
язык минимизации схем. потому что $L$ разрешима за полиномиальное время и потому , что, учитывая , тогда и только тогда , когда существует цепь $B$ таким образом, что для всех входов $х$ , . ${\ displaystyle {\ mathit {CM}} \ in \ Sigma _ {2} ^ {\ mathsf {P}} (= \ exists ^ {\ mathsf {P}} \ forall ^ {\ mathsf {P}} {\ mathsf {P}})}$ ${\ Displaystyle \ langle А, к \ rangle}$ ${\ displaystyle \ langle A, к \ rangle \ in {\ mathit {CM}}}$ ${\ displaystyle \ langle A, k, B, x \ rangle \ in L}$
Полная проблема для - выполнимость количественных булевых формул с k - 1 чередованием кванторов (сокращенно QBF _k или QSAT _k ). Это версия проблемы логической выполнимости для . В этой задаче нам дана булева формула f с переменными, разбитыми на k множеств X ₁ , ..., X _k . Мы должны определить, правда ли, что ${\ displaystyle \ Sigma _ {k} ^ {\ mathsf {P}}}$ ${\ displaystyle \ Sigma _ {k} ^ {\ mathsf {P}}}$
${\ Displaystyle \ существует X_ {1} \ forall X_ {2} \ exists X_ {3} \ ldots f}$
То есть существует ли такое присвоение значений переменным в X ₁ , что для всех присвоений значений в X ₂ существует присвоение значений переменным в X ₃ , ... f истинно? Вышеупомянутый вариант подходит для . Вариант, в котором первый квантор - «для всех», второй - «существует» и т. Д., Является полным для . Каждый язык является подмножеством задачи, полученной снятием ограничения на k - 1 чередование, PSPACE -полная задача TQBF . ${\ displaystyle \ Sigma _ {k} ^ {\ mathsf {P}}}$ ${\ displaystyle \ Pi _ {k} ^ {\ mathsf {P}}}$
В этом Сборнике можно найти список задач в стиле Гэри / Джонсона, которые, как известно, являются полными для второго и более высоких уровней полиномиальной иерархии .

Смотрите также

использованная литература

Общие ссылки

Арора, Санджив; Варак, Вооз (2009). Теория сложности: современный подход . Издательство Кембриджского университета. ISBN 978-0-521-42426-4. раздел 1.4, «Машины как струны и универсальная машина Тьюринга» и 1.7, «Доказательство теоремы 1.9».
А. Р. Мейер и Л. Дж. Стокмейер . Проблема эквивалентности регулярных выражений с возведением в квадрат требует экспоненциального пространства. В 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.

Languages

In other projects