El poder irracional de la no uniformidad

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. $\mathsf{P}$$\mathsf{NP}$$\mathsf{P}$

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.$\mathsf{P}$$\mathsf{P}/poly$$\mathsf{P}/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 P ⊆ P / p o l y .$\mathsf{NEXP}$$\mathsf{NEXP}$ $\mathsf{NP}$$\mathsf{NEXP}$$\mathsf{NEXP}\subseteq \mathsf{P}/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?

¡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 ⁿ 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.

$O(2^{2n})$$O(2^{n})$$n$$(1+o(1))2^n/n$$\mathsf{SIZE}(f(n))$$\mathsf{DTIME}(f(n)^{O(1)})$$f(n)$$2^{O(n)}$

$\mathsf{NP} \subseteq \mathsf{P/poly}$

$\mathbb{P/poly}$$\mathbb{NP}$$\mathbb{P}$$\mathbb{NP}$

$\mathbb{P/poly}$$\mathbb{NP}$

$\mathbb{NP}$

$\mathbb{NP}$$\mathbb{P/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.

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.

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.

$2^n$$n$$n$$n$$n$$2^n\exp(O(n))=\exp(n\log(2)+O(n))=\exp(O(n))$

$n$$\mathsf{NEXP}$

$\mathsf{P/poly'}\subseteq \mathsf{NP}$$n$$\mathsf{P/poly'}$$\mathsf{P}$$\mathsf{NP}\subseteq\mathsf{P/poly'}$) sigue siendo cierto, pero esta afirmación es menos interesante que el teorema real de Karp-Lipton.