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

Эта статья включает в себя список ссылок , связанных материалов или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Июль 2019 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

В теории сложности вычислений , то полиномиальная иерархия (иногда называются полиномиальное время иерархия ) является иерархией из классов сложности , обобщающих классы NP и со-NP . ^[1] Каждый класс в иерархии содержится в 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}}}}

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

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

Определение количественных логических формул [ править ]

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

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

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

\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 . $\left(\exists ^{p}L\right)^{\rm {c}}=\forall ^{p}L^{\rm {c}}$ $\left(\forall ^{p}L\right)^{\rm {c}}=\exists ^{p}L^{\rm {c}}$

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

\exists ^{\mathsf {P}}{\mathcal {C}}:=\left\{\exists ^{p}L\ |\ p{\text{ is a polynomial and }}L\in {\mathcal {C}}\right\}

\forall ^{\mathsf {P}}{\mathcal {C}}:=\left\{\forall ^{p}L\ |\ p{\text{ is a polynomial and }}L\in {\mathcal {C}}\right\}

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

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

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

\Sigma _{k+1}^{\mathsf {P}}:=\exists ^{\mathsf {P}}\Pi _{k}^{\mathsf {P}}

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

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

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

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

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

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

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

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

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

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

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

\Sigma _{i}^{\mathsf {P}}\subseteq \Delta _{i+1}^{\mathsf {P}}\subseteq \Sigma _{i+1}^{\mathsf {P}}

\Pi _{i}^{\mathsf {P}}\subseteq \Delta _{i+1}^{\mathsf {P}}\subseteq \Pi _{i+1}^{\mathsf {P}}

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

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

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

Отношения с другими классами [ править ]

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

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

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

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

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

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

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

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

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

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

Проблемы [ править ]

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

См. Также [ править ]

EXPTIME
Экспоненциальная иерархия
Арифметическая иерархия

Ссылки [ править ]

^ Arora и Barak, 2009, pp.97
^ Полнота в иерархии полиномиального времени A Compendium, M. Schaefer, C. Umans
^ 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»
А. Р. Мейер и Л. Дж. Стокмейер . Проблема эквивалентности регулярных выражений с возведением в квадрат требует экспоненциального пространства. В Proceedings of the 13th IEEE Symposium on Switching and Automata Theory , pp. 125–129, 1972. Статья, в которой была представлена полиномиальная иерархия.
LJ Stockmeyer . Полиномиальная иерархия . Теоретическая информатика , том 3, стр. 1–22, 1976.
C. Papadimitriou . Вычислительная сложность. Эддисон-Уэсли, 1994. Глава 17. Полиномиальная иерархия , стр. 409–438.
Майкл Р. Гэри и Дэвид С. Джонсон (1979). Компьютеры и непреодолимость: руководство по теории NP-полноты . WH Freeman. ISBN 0-7167-1045-5. Раздел 7.2: Полиномиальная иерархия, стр. 161–167.

Цитаты [ править ]

[1] Arora и Barak, 2009, pp.97

[2] Полнота в иерархии полиномиального времени A Compendium, M. Schaefer, C. Umans

[3] Arora и Barak, pp.99-100

[4] Арора и Барак, стр 100

[5] Арора и Барак, стр 100

[6] Арора и Барак, 2009, теорема 5.4.

[7] Hemaspaandra, Lane (2018). «17.5 Классы сложности». В Розене, Кеннет Х. (ред.). Справочник по дискретной и комбинаторной математике . Дискретная математика и ее приложения (2-е изд.). CRC Press. С. 1308–1314. ISBN 9781351644051.

[8] Арора и Барак, 2009, утверждение 5.5.

[1]

vтеВажные классы сложности ( подробнее )
Считается выполнимым	DLOGTIME AC 0 АКК 0 ТК 0 L SL RL NL NC SC CC п P-полный ЗПП RP BPP BQP APX
Подозревается в невозможности	ВВЕРХ НП НП-полный NP-жесткий со-НП совместно NP-полный ЯВЛЯЮСЬ QMA PH ⊕P PP #П # P-complete IP PSPACE PSPACE-полный
Считается невозможным	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME НАЧАЛЬНЫЙ PR р RE ВСЕ
Иерархии классов	Полиномиальная иерархия Экспоненциальная иерархия Иерархия Гжегорчика Арифметическая иерархия Логическая иерархия
Семьи классов	DTIME NTIME DSPACE NSPACE Вероятностно проверяемое доказательство Интерактивная система доказательств