Argumentos a favor / en contra de la conjetura de Kolmogorov sobre la complejidad del circuito de P

19

Según el relato histórico (no verificado), Kolmogorov pensó que cada lenguaje en P tiene una complejidad de circuito lineal. (Vea la pregunta anterior conjetura de Kolmogorov que P tiene circuitos de tamaño lineal .) Tenga en cuenta que esto implica PNP .

La conjetura de Kolmogorov, sin embargo, es probable que falle. Por ejemplo, Ryan Williams escribe en un artículo reciente : "La conjetura sería sorprendente, de ser cierta. Para los idiomas en P requieren n100100 veces, parece poco probable que la complejidad de tales problemas se reduzca mágicamente al tamaño O(n) , simplemente porque se puede diseñar un circuito diferente para cada longitud de entrada ".

Por otro lado, Andrey Kolmogorov (1903-1987) es ampliamente reconocido como uno de los principales matemáticos del siglo XX. Es bastante difícil imaginar que hubiera propuesto una conjetura completamente absurda. Por lo tanto, para entenderlo mejor, traté de encontrar algunos argumentos que realmente pudieran apoyar su sorprendente suposición. Esto es lo que podría pensar:

L P LPSIZE(lin)LPL

  1. Hay un conocido explícita algoritmo (máquina de Turing) que acepta L . De esto podemos construir una familia de funciones explícitas que debe tener una complejidad de circuito superlineal. Sin embargo, esto puede verse poco probable, ya que nadie ha sido capaz de encontrar ese ejemplo en más de 60 años de intensa investigación sobre circuitos.

  2. No se conoce ningún explícita algoritmo para L . Por ejemplo, su existencia se prueba por medios no constructivos, como el Axioma de Elección. O, incluso si existe el algoritmo explícito, nadie ha podido encontrarlo. Sin embargo, dado que hay infinitos idiomas que pueden desempeñar el papel de L , es poco probable que todos se comporten de esta manera hostil.

Pero luego, si descartamos ambas opciones como improbables, la única posibilidad restante es que tal L no exista. Eso significa PSIZE(lin) , que es precisamente la conjetura de Kolmogorov.

Pregunta: ¿Puedes pensar en algún otro argumento a favor / en contra de la conjetura de Kolmogorov?

Andras Farago
fuente
2
Me pregunto: ¿tenemos candidatos para refutar la conjetura de Kolmogorov? Por supuesto, uno puede considerar cualquier problema que probablemente tenga una complejidad superlineal. ¿Quizás algunos de ellos son más propensos a no tener circuitos de tamaño lineal?
Bruno
2
admitámoslo, nadie tiene la menor idea. (Re cita de Goldman en Hollywood: "nadie sabe nada"). La conjetura (inédita) puede haber estado abierta incluso más tiempo que P =? NP. sin embargo, vale la pena explorar una idea / ángulo aproximado: teoría de la compresión y compresibilidad. esto es básicamente a lo que williams alude y posiblemente podría estar en el corazón de muchas separaciones de clases de complejidad. La idea es que existen formas / algoritmos básicos para codificar datos, y algunos patrones son intrínsecamente más difíciles de comprimir utilizando codificaciones (arbitrarias) . pero también parece haber muy pocos resultados en esta área.
vzn
1
y por cierto, las muchas conexiones de la complejidad de Kolmogorov con la complejidad computacional, por ejemplo, exploradas por Fortnow, podrían tener alguna conexión explicativa de por qué las preguntas son tan difíciles de resolver, porque tantas preguntas relacionadas con la complejidad de Kolmogorov son indecidibles ...
vzn
1
@Bruno: Supongo que los problemas completos de serían buenos candidatos, por ejemplo, la programación lineal o el problema del valor del circuito. Si entonces estos problemas no pueden resolverse ni siquiera de manera no uniforme en tamaño poligonal y profundidad polilogármica, por lo que parece razonable suponer que tales problemas no deberían resolverse Soluble en tamaño lineal (y profundidad sin restricciones) tampoco. El determinante podría ser otro candidato razonable. Pero estas son solo propuestas: no tengo razones sólidas para pensar que tengan un tamaño de circuito superlineal. PN CPPNC
Joshua Grochow 01 de

Respuestas:

22

La nota de pie de página de mi artículo que usted cita se refiere también a un "argumento" heurístico, al menos, lo que creemos que fue la intuición de Kolmogorov: la resolución positiva del decimotercer problema de Hilbert.

http://en.wikipedia.org/wiki/Hilbert's_thirteenth_problem

En particular, Kolmogorov y Arnold demostraron que cualquier función continua en variables se puede expresar como una composición de funciones "simples": suma de dos variables y funciones continuas en una variable. Por lo tanto, sobre la "base" de las funciones continuas de una variable y la suma de dos variables, cada función continua en variables tiene "complejidad de circuito" .O ( n 2 ) n O ( n 2 )nO(n2)nO(n2)

Parece que Kolmogorov creía que existe un análogo discreto, donde "continuo en variables" se convierte en "booleano en variables y poli -tiempo computable", y donde la "base" dada anteriormente se convierte en funciones booleanas de dos variables.n ( n )nn(n)

Ryan Williams
fuente
Sería muy interesante si existiera el análogo discreto en el que Kolmogorov creía. Presumiblemente, los investigadores han tratado de encontrarlo, ya que podría conducir a una prueba de . ¿Cuál fue el obstáculo principal que encontraron? PNP
Andras Farago
3
Barricadas? No creo que nadie haya encontrado el camino :) Dado que la mayoría de las personas creen que no tiene circuitos de tamaño , por cada fijo , probablemente pocas personas hayan buscado el camino. O ( n k ) kPO(nk)k
Ryan Williams
11

La respuesta de Stasys a la pregunta anterior proporciona cierta intuición potencialmente a favor: /cstheory//a/22048/8243 . Trataré de repetir aquí como lo entiendo. La intuición clave es ver un circuito como, no un algoritmo, sino una codificación de un conjunto (el conjunto que acepta). Podemos obtener un límite superior en el tamaño de codificación mediante el tiempo de ejecución del algoritmo (es decir, traducir un time- TM en un circuito de tamaño- ), pero no está claro qué relación inversa debería existir. Si un idioma está en , entonces quizás esto implica que la membresía es lo suficientemente "local" como para codificarse de manera muy concisa.t PttP

Es decir, la pertenencia a es una declaración sobre el tiempo de ejecución de un algoritmo, mientras que los circuitos lineales son (quizás) una declaración sobre el tamaño de codificación de conjuntos de palabras de longitud fija. Ambas son declaraciones sobre la simplicidad del lenguaje, pero viven en mundos tal vez bastante diferentes.P

Otra intuición que menciona Stasys proviene de la "cadena indicadora" de un lenguaje, que formalicemos como la cadena infinita donde el bit es si la th cadena lexicográfica está en el idioma y es contrario. Un (polytime) TM para el lenguaje es un oráculo (rápido) para la cadena --- dado en binario, produce el bit . Un circuito (de tamaño lineal) para entradas de longitud es un oráculo (conciso) para el prefijo de longitud- de la cadena. La conjetura se convierte en "cualquier cadena infinita que tiene un oráculo 'rápido' tiene oráculos prefijos 'concisos'".1 j 0 j j n 2 nj1j0jjn2n

Ninguno de los anteriores explica por qué y" lineal "podrían ser los parámetros respectivos correctos para la declaración; pero creo que muestran esa intuición natural: que los circuitos actúan como algoritmos y requieren algoritmos más complicados circuitos igualmente complicados: pueden ser engañosos.P"

usul
fuente