El poder irracional de la no uniformidad

33

Desde el punto de sentido común de vista, es fácil creer que la adición de no determinismo a se extiende significativamente su potencia, es decir, N P es mucho mayor que P . Después de todo, el no determinismo permite el paralelismo exponencial, que sin duda parece muy poderoso. PNPP

Por otro lado, si solo agregamos no uniformidad a , obteniendo P / p o l y , entonces la intuición es menos clara (suponiendo que excluimos lenguajes no recursivos que podrían ocurrir en P / p o l y ). Uno podría esperar que simplemente permitir diferentes algoritmos de tiempo polinomiales para diferentes longitudes de entrada (pero no abandonar el ámbito recursivo) es una extensión menos poderosa que el paralelismo exponencial en el no determinismo.PP/polyP/poly

Curiosamente, sin embargo, si comparamos estas clases con la clase muy grande , entonces vemos la siguiente situación contraintuitiva. Sabemos que N E X P contiene correctamente N P , lo cual no es sorprendente. (Después de todo, N E X P permite un paralelismo doblemente exponencial). Por otro lado, actualmente no podemos descartar N E X PP / p o l y .NEXPNEXP NPNEXPNEXPP/poly

Por lo tanto, en este sentido, la falta de uniformidad, cuando se agrega al tiempo polinomial, posiblemente lo hace extremadamente poderoso, potencialmente más poderoso que el no determinismo. ¡Incluso podría llegar a simular un paralelismo doblemente exponencial ! Aunque creemos que este no es el caso, pero el hecho de que actualmente no se puede descartar aún sugiere que los teóricos de la complejidad están luchando con "poderes poderosos" aquí.

¿Cómo le explicaría a un laico inteligente qué hay detrás de este "poder irracional" de no uniformidad?

Andras Farago
fuente
16
La dificultad para comprender la no uniformidad (y probar los límites inferiores del circuito general) no implica necesariamente que la no uniformidad sea poderosa (en el sentido de que puede usarse para resolver problemas interesantes).
Kaveh
44
NEXPP/polyNPP/poly
8
EXPP/poly
2
O(n)P/polyP/poly
Joshua Grochow
66
Hacer eco de @thomas si no podemos probar que NEXP no está en P / poly significa que hay un "poder irracional de no uniformidad", ya que no podemos probar que P <> NP significa que debe haber un "poder irrazonable de computación eficiente".
Lance Fortnow

Respuestas:

33

¡Una respuesta negativa es que esto no es lo primero sobre la teoría de la complejidad que trataría de explicarle a un laico! Para incluso apreciar la idea de la no uniformidad, y cómo difiere del no determinismo, necesita estar más abajo en las malezas con las definiciones de clases de complejidad que muchas personas están dispuestas a obtener.

Una vez dicho esto, una perspectiva que he encontrado útil, al explicar P / poly a estudiantes universitarios, es que la no uniformidad realmente significa que puede tener una secuencia infinita de algoritmos mejores y mejores, a medida que avanza a longitudes de entrada cada vez más grandes. En la práctica, por ejemplo, sabemos que el algoritmo ingenuo de multiplicación de matrices funciona mejor para matrices de hasta 100x100, y luego, en algún momento, la multiplicación de Strassen mejora, y luego los algoritmos más recientes solo mejoran para matrices astronómicamente grandes que nunca surgiría en la práctica. Entonces, ¿qué pasaría si tuvieras la habilidad mágica de concentrarte en el mejor algoritmo para cualquier rango de n con el que estuvieras trabajando?

Claro, esa sería una habilidad extraña, y considerando todo, probablemente no tan útil como la capacidad de resolver problemas NP-completos en tiempo polinómico. Pero estrictamente hablando, sería una habilidad incomparable : no es una que obtendrías automáticamente incluso si P = NP. De hecho, incluso puede construir ejemplos artificiales de problemas inconfesables (por ejemplo, dado 0 n como entrada, ¿se detiene la enésima máquina de Turing?) Que esta habilidad le permitiría resolver. Entonces, ese es el poder de la no uniformidad.

Para entender el punto de considerar este extraño poder, probablemente deba decir algo sobre la búsqueda para probar los límites inferiores del circuito, y el hecho de que, desde el punto de vista de muchas de nuestras técnicas de límite inferior, es la uniformidad lo que parece extraño condición adicional que casi nunca necesitamos.

Scott Aaronson
fuente
2
P/polyBPPBPPNEXPBPP
77
¡BPP es mucho más fácil de motivar! Eso solo está tratando de modelar el poder de la aleatorización, que (a diferencia de la no uniformidad) es algo que se usa todo el tiempo en la práctica. (Incidentalmente, sin embargo, olvidé mencionar: una forma diferente de motivar la no uniformidad sería a través de la criptografía. Se podría señalar que los adversarios tienen el lujo de optimizar todos sus recursos de ataque para cualquier longitud clave que se haya elegido como estándar, por lo que Será mejor que tenga un criptosistema que considere seguro contra atacantes no uniformes a esa longitud fija, no solo contra atacantes uniformes.)
Scott Aaronson
1
BPPBPPNEXPBPPPP=BPPNEXPBPP
2
PEXPBPP
28

O(22n)O(2n)n(1+o(1))2n/nSIZE(f(n))DTIME(f(n)O(1))f(n)2O(n)

NPP/poly

Sasho Nikolov
fuente
1
¡Muy interesante! Ilustra muy bien que nuestra comprensión del modelo de cómputo no uniforme (circuito) aún está muy lejos de completarse.
Andras Farago
44
Sin comentar si es probable un colapso de este tipo: ¿es una parada repentina en el poder computacional en el segundo nivel, cuando esto es exactamente suficiente para tener ambos tipos de cuantificador?
Niel de Beaudrap
@NieldeBeaudrap Punto muy interesante. Por supuesto, todo esto (incluida la especulación en mi respuesta) es más teología que matemática, pero es divertido especular.
Sasho Nikolov
3
@ Sasho: no es teología, ni siquiera opinión: es proto-matemática, ¿no? Es un recuento de las ideas que posiblemente sean relevantes y sopesarlas para la intuición. No hay mucho más que hacer cuando se pierde en el bosque, pero es más productivo que, por ejemplo, contar historias de fantasmas. :-)
Niel de Beaudrap
10

P/polyNPPNP

P/polyNP

NP

NPP/poly

Un punto crítico para dar una buena comprensión, que creo que también es común cuando se enseña el tema por primera vez, es dejar claro que el consejo y la "pista" (es decir, el certificado) son cosas diferentes y cómo difieren.

chazisop
fuente
10

Para mí, la ilustración más clara del poder de la no uniformidad es que una versión adecuadamente acolchada del Problema de detención ya está en P / 1. Un solo consejo es suficiente para decidir este lenguaje con una TM trivial que simplemente devuelve el consejo.

Por supuesto, rellenar un lenguaje indecidible por una cantidad exponencial significa que no está "moralmente" en P / poly. Pero esto muestra que hay que tener cuidado al permitir la falta de uniformidad.

András Salamon
fuente
3

Tengo la impresión de que el problema real aquí es la pesada carga de la prueba irrazonable, no el poder irracional de la no uniformidad. Como las respuestas de chazisop y András Salamon ya enfatizan, los lenguajes indecidibles se vuelven computables incluso en lenguajes no uniformes muy restringidos, porque la carga de la prueba se ha renunciado por completo.

2nnnnn2nexp(O(n))=exp(nlog(2)+O(n))=exp(O(n))

nNEXP

P/polyNPnP/polyPNPP/poly) sigue siendo cierto, pero esta afirmación es menos interesante que el teorema real de Karp-Lipton.

Thomas Klimpel
fuente