¿Una buena referencia para operadores de clase de complejidad?

Me interesa si existen buenos artículos o encuestas expositivas a los que me pueda referir cuando escribo sobre operadores de clase de complejidad : operadores que transforman las clases de complejidad haciendo cosas como agregarles cuantificadores.

Ejemplos de operadores.

Lo siguiente se puede interpretar como una lista mínima mínima de operadores que una respuesta debería poder describir. Aquí, $\mathbf C$ es un conjunto arbitrario de lenguajes, sobre un alfabeto finito arbitrario . $\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.$

El operador aparentemente fue introducido por Wagner [1], aunque con la notación en lugar de . El ejemplo más famoso de una clase construido de esta manera es . Este operador viene con un cuantificador complementario , en el que en la definición se reemplaza por , que permite definir fácilmente la jerarquía polinómica completa: por ejemplo, . Posiblemente este sea el primer operador que se definió. $\exists$ $\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.$

El $\oplus$ operador es similar a la $\exists$ operador en que $\oplus\mathbf C$ se refiere a la cantidad de certificados que existen que son verificable en la clase $\mathbf C$ , pero en su lugar cuenta el número de Certficiates MODULO $2$ . Esto se puede utilizar para definir las clases $\mathsf{\oplus P}$ y $\mathsf{\oplus L}$ . Operadores similares " $\mathsf{Mod_k \cdot}$ " existen para otros módulos $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\}$

Este es el operador complementario, y se usa tácitamente para definir , , y una gran cantidad de otras clases de las que no se sabe que están cerradas bajo complementos. $\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.$

- con disculpas por el espacio

El operador aparentemente fue introducido por Schöning [2], aunque definió los lenguajes (es decir, no permitió un intervalo de probabilidad) y sin usar las constantes explícitas o . La definición aquí produce problemas prometedores, con YES-instance y NO-instance en . Tenga en cuenta que , y ; Toda y Ogiwara [3] utilizaron este operador para mostrar que . $\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}$

Observaciones

Otros operadores importantes que se pueden extraer de las definiciones de clases estándar son (de las clases y ) y (de las clases y ). También está implícito en la mayoría de la literatura que (generando problemas de función de las clases de decisión) y (generando clases de conteo de las clases de decisión) también son operadores de complejidad. $\mathsf{C_= \cdot\mathbf C}$ $\mathsf{C_= P}$ $\mathsf{C_= L}$ $\mathsf C\cdot\mathbf C$ $\mathsf{PP}$ $\mathsf{PL}$ $\mathsf{F\cdot}$ $\#\cdot$

Hay un artículo de Borchert y Silvestri [4] que propone definir un operador para cada clase, pero que no parece mencionarse demasiado en la literatura; También me preocupa que un enfoque tan general pueda tener problemas de definición sutiles. A su vez, se refieren a una buena presentación de Köbler, Schöning y Torán [5], que, sin embargo, ahora tiene más de 20 años y también parece perderse . $\oplus$

Pregunta

¿Qué libro o artículo es una buena referencia para los operadores de clase de complejidad?

Referencias

[1]: K. Wagner, La complejidad de los problemas combinatorios con representaciones de entrada sucintas , Acta Inform. 23 (1986) 325–356.

[2]: U. Schöning, Clases de complejidad probabilística y baja , en Proc. 2ª Conferencia del IEEE sobre la estructura en la teoría de la complejidad, 1987, pp. 2-8; también en J. Comput. System Sci., 39 (1989), págs. 84-100.

[3]: S. Toda y M. Ogiwara, las clases de conteo son al menos tan difíciles como la jerarquía de tiempo polinomial , SIAM J. Comput. 21 (1992) 316–328.

[4]: B. y Borchert, R. Silvestri, operadores de puntos, Theoretical Computer Science Volume 262 (2001), 501–523.

[5]: J. Köbler, U. Schöning y J. Torán, El problema del isomorfismo gráfico: su complejidad estructural, Birkhäuser, Basilea (1993).

reference-request complexity-classes Niel de Beaudrap
fuente

Un antecedente notable de la noción de operador de complejidad es el tratamiento de [6]: S. Zachos, cuantificadores probabilísticos, adversarios y clases de complejidad: una visión general, Proc. de la Conferencia sobre la Estructura en la Teoría de la Complejidad (pp.383-400), Berkeley, California, 1986, que Schöning [2] cita anteriormente en relación con .

B P \cdot N P

$\mathsf{BP\cdot NP}$

Niel de Beaudrap

De nuevo por Zachos, esto también podría ayudar: Complejidad combinatoria: Operadores en clases de complejidad

Alessandro Cosentino

@NieldeBeaudrap Zachos es el primero que surgió con la noción de operadores de clase de complejidad. Recuerdo de sus conferencias que él declaró explícitamente esto. También hay uno para mayoría abrumadora,

\exists^{+}

${\exists^+}$

Tayfun Pay

@TayfunPay: de hecho, el cuantificador

es útil para describir

, aunque utilizando el formalismo de dos lados descrito en [6] (en mi comentario anterior) en lugar de la forma descrita por Schöning.

\exists^{+}

$\exists^+$

B P \cdot

$\mathsf{BP\cdot}$

Niel de Beaudrap

@NieldeBeaudrap También es otro que se puede utilizar para definir sin límites de error de dos caras

\exists_{1 / 2}

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

Tayfun Pay

Respuestas:

Aquí hay una referencia con muchas definiciones de operadores (aunque no hay muchos detalles):

S. Zachos y A. Pagourtzis, Complejidad combinatoria: Operadores en clases de complejidad , Actas del 4º Simposio de lógica panhelénica (PLS 2003), Salónica, 7-10 de julio de 2003.

Define un operador de identidad , así como operadores -, (correspondiente a arriba), , (correspondiente a error unilateral acotado), , (correspondiente a no determinismo con una aceptación única transición), (correspondiente a un error de dos lados ilimitado) y (que para una clase forma ). $\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$
Muestra que:
1. es un elemento de identidad con respecto a la composición [Definición 1]; $\mathcal E$
2. - es autoinverso [Definición 2]; $\mathsf{co}$
3. es idempotente [Definición 3]: implícito es que , , , y también son idempotentes; $\mathsf{N}$ $\mathsf{BP}$ $\mathsf{R}$ $\oplus$ $\mathsf U$ $\mathsf{P}$
4. y conmutan con - [Definiciones 4 y 8], mientras que es invariable en la composición derecha con - [Definición 6]; $\mathsf{BP}$ $\mathsf{P}$ $\mathsf{co}$ $\oplus$ $\mathsf{co}$
5. Los operadores anteriores son todos monótonos (es decir, para todos los operadores anteriores): ${\mathbf C_1 \subseteq \mathbf C_2} \implies {\mathcal O\cdot\mathbf C_1 \subseteq \mathcal O\cdot\mathbf C_2}$ $\mathcal O$

En todo el documento, también describe algunas formas en que estos operadores se relacionan con las clases de complejidad tradicionales, como , , , , etc. $\mathsf{\Sigma^p_2 P}$ $\mathsf{ZPP}$ $\mathsf{AM}$ $\mathsf{MA}$

Alessandro Cosentino
fuente

Como referencia introductoria a la noción de operador de complejidad (y demostrando algunas aplicaciones de la idea), lo mejor que he encontrado hasta ahora es

D. Kozen, Teoría de la computación (Springer 2006)

que se deriva de las notas de clase sobre complejidad computacional y temas relacionados. En la página 187 ("Lección complementaria G: Teorema de Toda"), define los operadores

(para certificados aleatorios con error unilateral acotado, como en la clase ) $\mathsf R$ $\mathsf{RP}$
(para certificados aleatorios con error de dos lados acotado, ver arriba) $\mathsf{BP}$
(para certificados aleatorios con error ilimitado, cf en los comentarios anteriores) $\mathsf P$ $\mathsf C$
(para un número impar de certificados, ver arriba) $\oplus$
(para la existencia de certificados de longitud polinómica, cf arriba) $\Sigma^{\mathrm{p}}$ $\exists$
(para la existencia decertificados de longitud , cf arriba) $\Sigma^{\mathrm{log}}$ $O(\log n)$ $\exists$
y (operadores complementarios a y : ver comentarios en arriba) $\Pi^{\mathrm{p}}$ $\Pi^{\mathrm{log}}$ $\Sigma^{\mathrm{p}}$ $\Sigma^{\mathrm{log}}$ $\forall$
(definiendo una clase de conteo, cf comentarios anteriores) $\#$

y tácitamente define en la página 12 de la forma habitual. $\mathsf{co\text-}$

El tratamiento de Kozen de estos operadores es suficiente para indicar cómo están conectados con las clases de complejidad "habituales", y para describir el teorema de Toda, pero no discute mucho sobre sus relaciones y solo los menciona para un total de 6 páginas (en lo que es después de todo un libro que cubre un tema mucho más amplio). Esperemos que alguien pueda proporcionar una mejor referencia que esta.

Niel de Beaudrap
fuente