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

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

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

Определения

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

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

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

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

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

$\Delta _{i+1}^{\mathsf {P}}:={\mathsf {P}}^{\Sigma _{i}^{\mathsf {P}}}$

$\Sigma _{i+1}^{\mathsf {P}}:={\mathsf {NP}}^{\Sigma _{i}^{\mathsf {P}}}$

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

где ${\mathsf {P}}^{\rm {A}}$ — набор задач, решаемых за полиномиальное время с помощью машины Тьюринга , дополненной оракулом, для некоторой полной задачи класса 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}}}$ — класс задач, решаемых за полиномиальное время с помощью детерминированной машины Тьюринга с оракулом для некоторой 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\},$

где $\langle x,w\rangle \in \{0,1\}^{*}$ — это некое стандартное кодирование пары двоичных строк x и w как одной двоичной строки. Язык L представляет собой набор упорядоченных пар строк, где первая строка x является членом $\exists ^{p}L$, а вторая строка w является «короткой» ( $|w|\leq p(|x|)$) свидетель, показывающий, что x является членом $\exists ^{p}L$. Другими словами, $x\in \exists ^{p}L$ тогда и только тогда, когда существует короткий свидетель w такой, что $\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\}$

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

Пусть 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 можно определить как ${\mathsf {NP}}=\exists ^{\mathsf {P}}{\mathsf {P}}$, и ${\mathsf {coNP}}=\forall ^{\mathsf {P}}{\mathsf {P}}$, где 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 соответственно. Аналитическая иерархия также определяется аналогичным образом, чтобы дать иерархию подмножеств действительных чисел .

Определение альтернативных машин Тьюринга

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

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

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

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

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

Объединение всех классов полиномиальной иерархии представляет собой класс сложности 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}}$

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

• P = NP тогда и только тогда, когда P = PH .
• Если NP = co-NP, то NP = PH . ( совместный НП $\Pi _{1}^{\mathsf {P}}$.)

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

Нерешенная задача в информатике :

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

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

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

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

См. также: PH (сложность) § Связь с другими классами.

Нерешенная задача в информатике :

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

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

Диаграмма Хассе классов сложности, включая P , NP , co-NP , BPP , P/poly , PH и PSPACE.

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

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

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

Каждый класс в полиномиальной иерархии содержит $\leq _{\rm {m}}^{\mathsf {P}}$-полные проблемы (задачи, полные при полиномиальном времени редукции «много-единица»). Более того, каждый класс в полиномиальной иерархии замкнут при $\leq _{\rm {m}}^{\mathsf {P}}$-сокращения : это означает, что для класса C в иерархии и языке $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}}$. Другими словами, если язык определен на основе некоторого оракула в C что он определен на основе полной проблемы для C. , то мы можем предположить , Таким образом, полные задачи выступают «представителями» класса, для которого они полны.

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

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

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

Проблемы

• Пример естественной проблемы в $\Sigma _{2}^{\mathsf {P}}$ Минимизация схемы : по заданному числу k и схеме A, вычисляющей булеву функцию f , определить, существует ли схема с не более чем k элементами, которая вычисляет ту же функцию f . Пусть C — множество всех логических схем. Язык

  $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\}$

  — это язык минимизации схем. ${\mathit {CM}}\in \Sigma _{2}^{\mathsf {P}}(=\exists ^{\mathsf {P}}\forall ^{\mathsf {P}}{\mathsf {P}})$ поскольку L разрешимо за полиномиальное время и поскольку, учитывая $\langle A,k\rangle$, $\langle A,k\rangle \in {\mathit {CM}}$ тогда и только тогда, когда существует схема B такая, что для всех входов x , $\langle A,k,B,x\rangle \in L$.
• Полная проблема для $\Sigma _{k}^{\mathsf {P}}$ - выполнимость для кванторных булевых формул с k – 1 чередованием кванторов (сокращенно QBF _k или QSAT _k ). Это версия проблемы булевой выполнимости для $\Sigma _{k}^{\mathsf {P}}$. В этой задаче нам дана булева формула f с переменными, разбитыми на k наборов X ₁ , ..., X _k . Нам предстоит определить, правда ли, что

  $\exists X_{1}\forall X_{2}\exists X_{3}\ldots f$

  То есть существует ли присвоение значений переменным в X ₁ такое, что для всех присвоений значений в X ₂ существует присвоение значений переменным в X ₃ , ... f верно? Вариант выше подходит для $\Sigma _{k}^{\mathsf {P}}$. Вариант, в котором первый квантор «для всех», второй «существует» и т. д., является полным для $\Pi _{k}^{\mathsf {P}}$. Каждый язык представляет собой подмножество проблемы, полученной снятием ограничения на k – 1 чередование, PSPACE -полной задачи TQBF .
• Список задач в стиле Гэри/Джонсона, который, как известно, является полным для второго и более высокие уровни полиномиальной иерархии можно найти в этом Сборнике .

См. также

• ВРЕМЯ ЭКСПРЕСС
• Экспоненциальная иерархия
• Арифметическая иерархия

Ссылки

Общие ссылки

1. Арора, Санджив; Барак, Вооз (2009). Теория сложности: современный подход . Издательство Кембриджского университета. ISBN  978-0-521-42426-4 . раздел 1.4 «Машины как струны и универсальная машина Тьюринга» и 1.7 «Доказательство теоремы 1.9»
2. А. Р. Мейер и Л. Дж. Стокмейер . Проблема эквивалентности регулярных выражений с возведением в квадрат требует экспоненциального пространства. В материалах 13-го симпозиума IEEE по теории коммутации и автоматов , стр. 125–129, 1972. Статья, в которой была представлена ​​полиномиальная иерархия.
3. Эл Джей Стокмейер . Иерархия полиномиального времени . Теоретическая информатика , том 3, стр. 1–22, 1976.
4. К. Пападимитриу . Вычислительная сложность. Аддисон-Уэсли, 1994. Глава 17. Полиномиальная иерархия , стр. 409–438.
5. Майкл Р. Гари и Дэвид С. Джонсон (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . У. Х. Фриман. ISBN  0-7167-1045-5 . Раздел 7.2: Полиномиальная иерархия, стр. 161–167.