Хорошая ссылка для операторов класса сложности?

Мне интересно, существуют ли какие-нибудь хорошие пояснительные статьи или обзоры, на которые я могу сослаться, когда пишу об операторах класса сложности : операторах, которые преобразуют классы сложности, выполняя такие вещи, как добавление к ним кванторов.

Примеры операторов

Следующее может быть истолковано как минимальный список операторов, который должен уметь дать ответ. Здесь $\mathbf C$ - произвольный набор языков над произвольным конечным алфавитом $\Sigma$ .

$\exists \mathbf C := \left\{ L \subseteq \Sigma^\ast \,\left|\, \begin{array}{l} \exists A \in \mathbf C \;\exists f \in O(\mathrm{poly}(n))\;\forall x \in \Sigma^\ast: \\\quad \bigl[x \in L \iff \exists c \in \Sigma^{f(|x|)}: (x,c) \in A \bigr] \end{array} \right\}\right.$

$\exists$ оператор был введен , по- видимому Вагнера [1], хотя и с обозначениями $\bigvee\! \mathbf C$ , а не $\exists \mathbf C$ . Самый известный пример классапостроенный таким образомявляется $\mathsf{NP} = \exists \mathsf P$ . Этот оператор приходит с дополнительным квантором $\forall$ , в котором $\exists c$ в определении заменяется $\forall c$ , что позволяет легко определить весь многочлен иерархии: например,. Это может быть первый оператор, который был определен. $\mathsf{\Sigma_2^P P = \exists \forall P}$

$\oplus \mathbf C := \left\{ L \subseteq \Sigma^\ast \,\left|\, \begin{array}{l} \exists A \in \mathbf C \;\exists f \in O(\mathrm{poly}(n)) \;\forall x \in \Sigma^\ast: \\ \quad\bigl[x \in L \iff \#\{ c \in \Sigma^{f(|x|)}: (x,c) \in A \} \not\equiv 0 \pmod{2}\bigr]\end{array} \right\}\right.$

оператор похож на оператор в том , что касается количества сертификатов , которые существуют, которые проверяемые в классе , но вместо этого подсчитывает количество certficiates по модулю . Это можно использовать для определения классов и . Аналогичные операторы " " существуют для других модулей . $\oplus$ $\exists$ $\oplus\mathbf C$ $\mathbf C$ $2$ $\mathsf{\oplus P}$ $\mathsf{\oplus L}$ $\mathsf{Mod_k \cdot}$ $k$

$\mathsf{co}\mathbf C := \Bigl\{ L \subseteq \Sigma^\ast \,\Big|\, \exists A \in \mathbf C \;\forall x \in \Sigma^\ast: \bigl[x \in L \iff x \notin A \bigr] \Bigr\}$

Это дополнительный оператор, и он молчаливо используется для определения , , и множества других классов из классов, которые, как известно, не закрыты в дополнениях. $\mathsf{ coNP}$ $\mathsf{coC_=P}$ $\mathsf{coMod_kL}$

$\mathsf{BP}\cdot\mathbf C := \left\{ (\Pi_0, \Pi_1) \,\left|\, \begin{array}{l} \Pi_0, \Pi_1 \subseteq \Sigma^\ast \;\mathbin\&\; \exists A \in \mathbf C \; \exists f \in O(\mathrm{poly}(n))\;\forall x \in \Sigma^\ast: \\ \quad\left[\begin{array}{l} \bigl(x \in \Pi_0 \Leftrightarrow \#\{c \in \Sigma^{f(|x|)}: (x,c) \in A \} \leqslant \tfrac{1}{3} {|\Sigma^{f(|x|)}|} \bigr) \mathbin\& \\ \bigl(x \in \Pi_1 \Leftrightarrow \#\{c \in \Sigma^{f(|x|)}: (x,c) \in A \} \geqslant \tfrac{2}{3} {|\Sigma^{f(|x|)}|} \bigr) \end{array}\right]\end{array}\right\}\right.$

- с извинениями за расстояние

Оператор видимому, был введен Шенингом [2], хотя и для определения языков (т. Е. Он не допустил разрыв вероятности) и без использования явных констант или . Здесь определение вместо этого приводит к проблемам обещания с YES-экземплярами и NO-экземплярами в . Обратите внимание, что и ; Тода и Огивара [3] использовали этот оператор, чтобы показать, что $\mathsf{BP}$ $\tfrac{1}{3}$ $\frac{2}{3}$ $\Pi_1$ $\Pi_0$ $\mathsf{BPP = BP\cdot P}$ $\mathsf{AM = BP\cdot NP}$ $\mathsf{P^{\#P} \subseteq BP\cdot\oplus P}$ .

замечания

Другими важными операторами, которые можно абстрагировать от определений стандартных классов, являются (из классов и ) и (из классов и ). В большинстве литературы также подразумевается, что (порождающий функциональные проблемы из классов решений) и $\mathsf{C_= \cdot\mathbf C}$ $\mathsf{C_= P}$ $\mathsf{C_= L}$ $\mathsf C\cdot\mathbf C$ $\mathsf{PP}$ $\mathsf{PL}$ $\mathsf{F\cdot}$ $\#\cdot$ (порождающие счетные классы из классов решений) также являются операторами сложности.

Существует статья Борхерта и Сильвестри [4], в которой предлагается определить оператор для каждого класса, но в литературе, по-видимому, на нее мало ссылаются; Я также волнуюсь, что такой общий подход может иметь тонкие проблемы определения. Они, в свою очередь, ссылаются на хорошую презентацию Коблера, Шенинга и Торана [5], которой, однако, уже более 20 лет, и, похоже, она также отсутствует $\oplus$ .

Вопрос

Какая книга или статья является хорошим справочником для операторов класса сложности?

Ссылки

[1]: К. Вагнер, Сложность комбинаторных задач с краткими входными представлениями , Acta Inform. 23 (1986) 325–356.

[2]: У. Шенинг, Вероятностные классы сложности и малости , в Proc. 2-я конференция IEEE по структуре в теории сложности, 1987, с. 2-8; также в J. Comput. System Sci., 39 (1989), с. 84-100.

[3]: С. Тода и М. Огивара. Подсчет классов по меньшей мере так же сложен, как и иерархия полиномиального времени , SIAM J. Comput. 21 (1992) 316–328.

[4]: Б. и Борхерт, Р. Сильвестри, Точечные операторы , Теоретическая информатика, том 262 (2001), 501–523.

[5]: J. Köbler, U. Schöning, J. Torán, Проблема изоморфизма графов: ее структурная сложность, Birkhäuser, Basel (1993).

reference-request complexity-classes Ниль де Бодрап
источник

Примечательным предшественником понятия оператора сложности является обработка [6]: S. Zachos, Вероятностные квантификаторы, Противники и Классы сложности: Обзор, Proc. конференции по структуре в теории сложности (стр. 383-400), Беркли, Калифорния, 1986, которая цитируется Шенингом [2] выше в связи с .

B P \cdot N P

$\mathsf{BP\cdot NP}$

Ниль де Бодрап,

Снова Zachos, это также может помочь: Комбинаторная сложность: операторы на классах сложности

Алессандро Косентино

@NieldeBeaudrap Zachos - это тот, кто первым предложил понятие операторов класса сложности. Я помню из его лекций, что он прямо заявил об этом. Существует также один для подавляющего большинства, .

\exists^{+}

${\exists^+}$

Tayfun Pay

@TayfunPay: действительно, квантификатор exist полезен для описания , хотя и использует двусторонний формализм, описанный в [6] (в моем комментарии выше), а не способ, описанный Шенингом.

\exists^{+}

$\exists^+$

B P \cdot

$\mathsf{BP\cdot}$

Ниль де Бодрап,

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

\exists_{1 / 2}

${\exists _{1/2}}$

Tayfun Pay

Ответы:

Вот ссылка со многими определениями операторов (хотя не так много деталей):

С. Zachos и A. Pagourtzis, комбинаторная сложность: операторы на классах сложности , материалы 4-го Панелленического логического симпозиума (PLS 2003), Салоники, 7-10 июля 2003 г.

Он определяет тождественный оператор , а также операторы -, (соответствует выше), , (соответствует ограниченной односторонней ошибке), , (соответствует недетерминизму с единственным принятием переход), (соответствует неограниченной двусторонней ошибке) и (который для класса образует ). $\mathcal E$ $\mathsf{co}$ $\mathsf{N}$ $\exists$ $\mathsf{BP}$ $\mathsf{R}$ $\oplus$ $\mathsf U$ $\mathsf P$ $\Delta$ $\mathbf C$ $\mathbf C \cap \mathsf{co}\mathbf C$
Это показывает, что:
1. является единичным элементом по отношению к композиции [определение 1]; $\mathcal E$
2. - самообратный [Определение 2]; $\mathsf{co}$
3. идемпотентен [Определение 3] - подразумевается, что , , , и также идемпотентны; $\mathsf{N}$ $\mathsf{BP}$ $\mathsf{R}$ $\oplus$ $\mathsf U$ $\mathsf{P}$
4. и коммутируют с - [определения 4 и 8], а инвариантен относительно правой композиции с - [определение 6]; $\mathsf{BP}$ $\mathsf{P}$ $\mathsf{co}$ $\oplus$ $\mathsf{co}$
5. Все вышеперечисленные операторы являются монотонными (то есть для всехвышеперечисленныхоператоров ): ${\mathbf C_1 \subseteq \mathbf C_2} \implies {\mathcal O\cdot\mathbf C_1 \subseteq \mathcal O\cdot\mathbf C_2}$ $\mathcal O$

В нем также описывается несколько способов, которыми эти операторы относятся к традиционным классам сложности, таким как , , , и т. Д. $\mathsf{\Sigma^p_2 P}$ $\mathsf{ZPP}$ $\mathsf{AM}$ $\mathsf{MA}$

Алессандро Косентино
источник

В качестве вводной ссылки на понятие оператора сложности (и демонстрации некоторых применений этой идеи) лучшее, что я нашел до сих пор, это

Д. Козен, Теория вычислений (Springer 2006)

который получен из примечаний лекции по вычислительной сложности и связанным темам. На странице 187 («Дополнительная лекция G: Теорема Тоды») он определяет операторы

(для случайных сертификатов с ограниченной односторонней ошибкой, как в классе ) $\mathsf R$ $\mathsf{RP}$
(для случайных сертификатов с ограниченной двусторонней ошибкой см. Выше) $\mathsf{BP}$
(для случайных сертификатов с неограниченной ошибкой, cf в примечаниях выше) $\mathsf P$ $\mathsf C$
(нечетное количество сертификатов см. Выше) $\oplus$
(для существования сертификатов полиномиальной длины, CF выше) $\Sigma^{\mathrm{p}}$ $\exists$
(для существования -длина сертификатов, ср выше) $\Sigma^{\mathrm{log}}$ $O(\log n)$ $\exists$
и (дополнительные операторы к и : см замечания по выше) $\Pi^{\mathrm{p}}$ $\Pi^{\mathrm{log}}$ $\Sigma^{\mathrm{p}}$ $\Sigma^{\mathrm{log}}$ $\forall$
(определение класса подсчета, см. примечания выше) $\#$

и негласно определяет на странице 12 в обычном порядке. $\mathsf{co\text-}$

Обработка этих операторов Козеном достаточна, чтобы указать, как они связаны с «обычными» классами сложности, и описать теорему Тоды, но мало обсуждает их отношения и упоминает их всего на 6 страницах (в конце концов, книга, охватывающая гораздо более широкую тему). Надеюсь, кто-то может предоставить лучшую ссылку, чем эта.

Ниль де Бодрап
источник