¿Qué problemas de

La famosa Imagen del mundo de Neil Immerman es la siguiente (haga clic para ampliar):

Su clase "Verdaderamente factible" no incluye ninguna otra clase; mi pregunta es entonces:

¿Qué es un problema de AC ⁰ que se considera poco práctico y por qué?

cc.complexity-theory circuit-complexity Michaël Cadilhac
fuente

¿Quizás un problema que requiere circuitos de profundidad 10 ^ {10 ^ 100}?

Tsuyoshi Ito

@Ross: No lo creo porque no mencionó "mundo real" y preguntó "por qué"; Creo que mi comentario anterior responde al menos a la parte "por qué". Sin embargo, es cierto que no tengo un ejemplo de problemas "naturales" que están en AC0 y requieren circuitos de profundidad 10 ^ {10 ^ 100}.

Tsuyoshi Ito

Existen numerosos problemas interesantes del mundo real que podrían resolverse en un tiempo constante y en un espacio constante (en prácticamente cualquier modelo de computación), sin embargo, las personas ahora tienen idea de cómo resolverlos en la práctica. Ejemplos extremos son el cálculo de ciertas constantes; podríamos codificar la respuesta correcta (por ejemplo, 0 o 1), pero aún no sabemos la respuesta.

Jukka Suomela

Jukka: esas son instancias problemáticas. Las ecuaciones de diofantina (como la de Fermat) son indecidibles como clase, incluso si las instancias individuales que hemos decidido tienen circuitos de profundidad constante.

András Salamon

@ András: Si prefiere problemas de decisión con infinidad de instancias de "sí" y "no": deje que

consista en todos los números pares

, donde

si el jugador blanco tiene una estrategia ganadora en el ajedrez y de lo contrario

. Trivialmente, existe una familia muy simple de circuitos que decide

, pero todavía afirmaría que es "poco práctico". No porque el circuito sería enorme, sino porque diseñar el circuito sería un gran esfuerzo computacional ... ¿

L

$L$

x

$x$

x = 1

$x = 1$

x = 3

$x = 3$

L

$L$

Hacer

Respuestas:

Si desea un ejemplo de una función AC ⁰ que requiere profundidad , y no puede ser calculada por circuitos AC ⁰ de profundidad , pruebe las funciones Sipser . El superíndice es la profundidad necesaria para un circuito AC ^{0 de} tamaño polinómico . Con la profundidad , el circuito necesitaría exponencialmente muchas puertas. $d$ $d-1$ $S^{d,n}$ $d$ $d-1$

Por lo tanto, calcular para no sería "realmente factible". $S^{d,n}$ $d = 10^{10^{100}}$

EDITAR: Su pregunta también pregunta por qué esto no sería factible. Supongo que la razón es que es más que el número de átomos en el universo visible. $10^{10^{100}}$

Robin Kothari
fuente

¡Eso es genial, Gracias! ¿Quizás pueda agregar una definición informal de las funciones Sipser? No sabía sobre ese nombre.

Michaël Cadilhac

@ Michaël: Desafortunadamente no tengo una buena definición intuitiva para las funciones Sipser. La idea es hacer una función de cuantificadores d de manera que ningún circuito d-1 de profundidad pueda calcularlo. Por lo tanto, queremos que los cuantificadores d cuantifiquen sobre un gran número de variables. Hay un buen artículo de Iddo Tzameret, titulado "Separación de Håstad de circuitos de profundidad constante utilizando funciones Sipser" ( itcs.tsinghua.edu.cn/~tzameret/SipserSwitching.pdf ) que define formalmente las funciones en la página 7.

Robin Kothari

Toda esta jerarquía es intencionalmente robusta bajo cambios polinómicos del tamaño de entrada. Por lo tanto, cualquier clase puede contener funciones cuya complejidad es, digamos, n ^ {1000000000} que sería teóricamente "factible", pero ciertamente no prácticamente. Sin embargo, estos probablemente serán problemas muy artificiales. En particular, mediante un argumento de conteo existe una familia de fórmulas DNF (= AC ^ 0 profundidad 2 circuitos) de tamaño n ^ 1000000 que ningún algoritmo cuyo tiempo de ejecución es menor que n ^ 999999 puede calcular. (En un entorno uniforme, esperamos algo similar pero no podemos probarlo).

Noam
fuente

El problema de detención cuando la entrada está representada en unario está en AC ^ 0 y, sin embargo, es bastante inviable en realidad. No estoy seguro de que esto sea lo que quisiste decir, pero podría ser lo que quería decir Immerman.

Elad
fuente

¿Supongo que las clases en el diagrama están definidas con alguna noción de uniformidad? De lo contrario, la dirección hacia arriba no representaría la contención, ya que P no contiene AC ^ 0 no uniforme.

Robin Kothari

A C^{0}

$AC^0$

{0, 1}

$\{0,1\}$

{0, m a x; X, B I T, \leq, =}

$\{0,max; X,BIT,\le,=\}$

X

$X$

Punto bien tomado. Como alternativa, siguiendo a Erdos, uno podría sugerir el problema de que, para cualquier entrada, genera el número de Ramsey para el seis rojo y el seis azul.

Elad