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

Концепция компьютерной науки

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

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

Определения

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

Определение Оракула

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

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

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

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

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

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

где — множество задач принятия решений, решаемых за полиномиальное время машиной Тьюринга , дополненной оракулом для некоторой полной задачи из класса A; классы и определяются аналогично. Например, , а — класс задач, решаемых за полиномиальное время детерминированной машиной Тьюринга с оракулом для некоторой NP-полной задачи. ^[2] ${\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 \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 — «короткий» ( ) свидетель, свидетельствующий, что x является членом . Другими словами, тогда и только тогда, когда существует короткий свидетель w такой, что . Аналогично, определим ${\displaystyle \langle x,w\rangle \in \{0,1\}^{*}}$ ${\displaystyle \exists ^{p}L}$ ${\displaystyle |w|\leq p(|x|)}$ ${\displaystyle \exists ^{p}L}$ ${\displaystyle x\in \exists ^{p}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 ^c — дополнение L . ${\displaystyle \left(\exists ^{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{ is a polynomial and }}L\in {\mathcal {C}}\right\}}$

${\displaystyle \forall ^{\mathsf {P}}{\mathcal {C}}:=\left\{\forall ^{p}L\ |\ p{\text{ is a polynomial and }}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}}=\exists ^{\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 _{k+1}^{\mathsf {P}}:=\exists ^{\mathsf {P}}\Pi _{k}^{\mathsf {P}}}$

${\displaystyle \Pi _{k+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 , соответственно. Аналитическая иерархия также определяется аналогичным образом, чтобы дать иерархию подмножеств действительных чисел .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проблемы

• Примером естественной проблемы в является минимизация схемы : задано число k и схема A, вычисляющая булеву функцию f , определить, существует ли схема с не более чем k вентилями, которая вычисляет ту же функцию f . Пусть 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{ has at most }}k{\text{ gates, and }}A(x)=B(x)\right.\right\}}$

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

  ${\displaystyle {\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 такая, что для всех входов x , . ${\displaystyle {\mathit {CM}}\in \Sigma _{2}^{\mathsf {P}}(=\exists ^{\mathsf {P}}\forall ^{\mathsf {P}}{\mathsf {P}})}$ ${\displaystyle \langle A,k\rangle }$ ${\displaystyle \langle A,k\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 \exists 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}}}$
• Список задач в стиле Гэри/Джонсона, которые, как известно, являются полными для второго и более высоких уровней полиномиальной иерархии, можно найти в этом Компендиуме.

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

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

Ссылки

Общие ссылки

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

Цитаты

1. Арора и Барак, 2009, стр.97.
2. Полнота в иерархии полиномиального времени. Сборник, М. Шефер, К. Уманс
3. Арора и Барак, стр. 99–100.
4. Арора и Барак, стр.100
5. Арора и Барак, стр.100
6. Арора и Барак, 2009, Теорема 5.4
7. Hemaspaandra, Lane (2018). "17.5 Классы сложности". В Rosen, Kenneth H. (ред.). Handbook of Discrete and Combinatory Mathematics . Discrete Mathematics and Its Applications (2-е изд.). CRC Press. стр. 1308–1314. ISBN 9781351644051.
8. Ферраротти, Флавио; Ван ден Буше, Ян; Виртема, Джонни (2018). «Выразительность в логике транзитивного замыкания второго порядка». DROPS-IDN/V2/Document/10.4230/LIPIcs.CSL.2018.22 . Шлосс-Дагштуль - Центр информатики Лейбница. дои : 10.4230/LIPIcs.CSL.2018.22 . S2CID  4903744.
9. Арора и Барак, 2009, Утверждение 5.5