Usando la complejidad de Kolmogorov como "tamaño" de entrada

Digamos que tenemos un problema de cálculo, por ejemplo, 3-SAT, que tiene un conjunto de instancias de problemas (posibles entradas) . Normalmente en el análisis de algoritmos o teoría de la complejidad computacional, tenemos algunos conjuntos de todas las entradas de longitud , y una función que proporciona el tiempo de ejecución de algún algoritmo de solución en la entrada . La secuencia de tiempo de ejecución en el peor de los casos para es entonces $S$

I (n) = {w \in S : | w | = n}

$I(n) = \{w \in S : |w| = n\}$

n

$n$

T (w)

$T(w)$

A

$A$

w

$w$

A

$A$

f_{n} = max_{w \in I (n)} T (w) .

$f_n = \max_{w \in I(n)} T(w).$

Definamos ahora los conjuntos

I^{K} (n) = {w \in S : K (w) = n}

$I^K(n) = \{w \in S : K(w) = n \}$ de todas las entradas con complejidad de Kolmogorov

n

$n$ , y definamos la secuencia

f_{n}^{K} = \frac{1}{| I^{K} (n) |} \sum_{w \in I^{K} (n)} T (w) .

$f^K_n = \frac{1}{\left|I^K(n)\right|} \sum_{w \in I^K(n)} T(w).$ Aquí

f^{K}

$f^K$ es la secuencia de tiempo de ejecución promedio para

A

$A$ , excepto donde el "tamaño" de las entradas es su complejidad de Kolmogorov, no su longitud.

¿Existen algoritmos para los cuales $f_n$ es asintóticamente significativamente diferente de $f^K_n$ ? Si es así, ¿hay problemas cuya complejidad temporal cambia cuando se utiliza esta forma diferente de analizar algoritmos?

cc.complexity-theory kolmogorov-complexity parameterized-complexity succinct analysis-of-algorithms Andrés
fuente

Gran pregunta! Uno que a menudo me he preguntado, espero que obtenga algunas buenas respuestas. (Agregué la etiqueta parametrizada-complejidad b / c puede ver esto como la cuestión de la complejidad parametrizada de, por ejemplo, SAT, donde el parámetro es la complejidad de Kolmogorov.)

Joshua Grochow

Las cadenas aleatorias, alias la mayoría de las cadenas, tienen una complejidad de Kolmogorov cerca de su longitud original. Para la gran mayoría de las entradas

f_{n} = f_{n}^{K}

$f_{n} = f_{n}^{K}$ Puede obtener un resultado más interesante si pregunta sobre la profundidad computacional en lugar de la complejidad de Kolmogorov. google.com/…

Chad Brewbaker

Al mezclar algunas instancias de PARITY en un lenguaje difícil para formar

S

$S$ (por ejemplo, prefijando cada instancia con un conmutador de bits que describe de qué idioma es la instancia), entonces

f_{n}^{K}

$f^K_n$ será menor que

f_{n}

$f_n$ . Cuán pequeño depende de la densidad relativa.

András Salamon

Un lugar está en las notas de conferencia de Vadhan aquí (19 de febrero): people.seas.harvard.edu/~salil/cs221/spring10/lectures.html

usul

@ AndrásSalamon, sí, espero no ser demasiado descuidado, pero creo quedebería ser esencialmente la función de castor ocupado.

n \mapsto max_{w : K (w) = n} | w |

$n \mapsto \max_{w: K(w)=n} |w|$

usul

Respuestas:

Considere la función de paridad (o cualquier otra función que dependa de todos / la mayoría de los bits de la entrada). Para la función de paridad, . Entonces Por otro lado, $T(w) = \Theta(|w|)$

f_{n} = Θ (n) .

$f_n = \Theta(n).$

f_{n}^{K} = Θ (\frac{1}{| I^{K} (n) |} \sum_{w : K (w) = n} | w |) \geq Ω (\frac{1}{2^{n}} max_{w : K (w) = n} | w |) .

$f_n^K = \Theta\left(\frac{1}{|I^K(n)|} \sum_{w:K(w) = n} |w|\right) \geq \Omega\left(\frac{1}{2^n} \max_{w:K(w) = n} |w|\right).$

Tenga en cuenta que . Por lo tanto, y . Del mismo modo, ; así "crece muy rápidamente". Por otra parte, no es difícil ver que no hay límite superior para computable . $K(2^{2^n}) = O(n)$

max_{w : K (w) = n} | w | \geq 2^{2^{Ω (n)}}

$\max_{w:K(w) = n} |w| \geq 2^{2^{\Omega(n)}}$

f_{n}^{K} \geq 2^{2^{Ω (n)}} / 2^{n} \to \infty

$f_n^K \geq 2^{2^{\Omega(n)}} / 2^n \to \infty$

K (2^{\dots^{2^{2^{n}}}}) = O (n)

$K(2^{\dots^{2^{2^n}}}) = O(n)$

f_{n}^{K} \geq 2^{\dots^{2^{2^{Ω (n)}}}} / 2^{n}

$f_n^K \geq 2^{\dots^{2^{2^{\Omega(n)}}}}/2^n$

f_{n}^{K}

$f_n^K$

Yury
fuente

Dado el interés en esta pregunta, pensé que podría ser útil señalar más explícitamente la razón por la que no deberíamos sorprendernos en absoluto con la respuesta e intentar dar alguna dirección para los refinamientos de la pregunta. Esto recopila y amplía algunos comentarios. Pido disculpas si esto es "obvio"!

Considere el conjunto de cadenas de complejidad de Kolmogorov : Hay como máximo tales cadenas, ya que hay descripciones de longitud . Pero tenga en cuenta que este conjunto es indecidible para general (de lo contrario, podríamos calcular simplemente iterando de a y comprobando la pertenencia a ). Además, la función Crece indiscutiblemente rápido. Es una variante de la función de castor ocupado: ¿cuál es la salida más larga de una máquina Turing de longitud descriptiva $n$

J^{K} (n) = {w : K (w) = n} .

$J^K(n) = \{w : K(w) = n\}.$

2^{n}

$2^n$

2^{n}

$2^n$

n

$n$

n

$n$

K (w)

$K(w)$

n = 1

$n=1$

| w |

$|w|$

J^{K} (n)

$J^K(n)$

g^{K} (n) = max_{w \in J^{K} (n)} | w |

$g^K(n) = \max_{w \in J^K(n)} |w|$

n

$n$ ? Si esto se hizo más lento que alguna función computable, podríamos decidir el problema de detención: dada una TM , construya que simule e imprima un en cada paso. Si la longitud de la descripción de es , entonces: detiene a lo sumo pasos; o no se detiene.

M

$M$

M^{'}

$M'$

M

$M$

1

$1$

M^{'}

$M'$

n

$n$

M

$M$

g^{K} (n)

$g^K(n)$

M

$M$

Ahora, a la pregunta de Andrew, tenemos que , donde es el lenguaje original. Entonces, la única forma de evitar que contenga entradas muy grandes en sería si contiene solo cadenas muy incompresibles. (Tenga en cuenta que, de lo contrario, podemos ignorar por completo la distinción entre el análisis del caso más desfavorable y el caso medio, porque promediamos como máximo cadenas pero el tamaño de la cadena más grande está creciendo más rápido que cualquier función computable de . ) $I^K(n) = S \cap J^K(n)$ $S$ $I^K(n)$ $n$ $S$ $2^n$ $n$

Creo que es probable que sea imposible construir cualquier no trivial (es decir, infinita) que contenga solo cadenas no comprimibles, pero que sea decidible. Pero no lo se. Sin embargo, es de esperar que esto dé una intuición de por qué no deberíamos esperar que la mayoría de los idiomas tengan creciendo más lentamente que una función computable. $S$ $f^K_n$

Para retroceder un poco, la pregunta es comparar el rendimiento en las entradas de longitud con el rendimiento en las entradas que se pueden comprimir a la longitud . Pero tenemos nociones de compresión que son mucho más manejables (y menos potentes) que la complejidad de Kolmogorov. Una manera simple es dar un circuito de tamaño , que en la entrada el número binario produce el bit de . Tenga en cuenta que aquí el aumento en el tamaño de entrada es como máximo exponencial (un circuito de tamaño tiene como máximo entradas posibles). $n$ $n$ $n$ $b$ $b$ $w$ $n$ $2^n$

Entonces podemos reformular la pregunta dejando Y defina análoga. La razón de la esperanza aquí es que la mayoría de las cadenas requieren un circuito casi tan grande como la cadena misma, y ninguna cadena es más que exponencialmente más grande que el circuito requerido. Quizás en este caso podríamos encontrar lenguajes donde y son similares asintóticamente.

I^{C} (n) = {w \in S : the smallest circuit implicitly specifying w has size n} .

$I^C(n) = \{ w \in S : \text{the smallest circuit implicitly specifying $w$ has size $n$}\}.$

f_{n}^{C}

$f^C_n$

f_{n}

$f_n$

f_{n}^{C}

$f^C_n$

Una pregunta muy relacionada es la complejidad de los lenguajes implícitos como IMPLICIT_SAT es NEXP-complete y, por lo general, la versión implícita de los problemas de NP-complete es NEXP-complete. Decidir IMPLICIT_SAT es al menos tan fácil como usar el circuito para escribir todo y luego ejecutar un algoritmo para SAT en . Entonces, si para SAT, entonces esto parece cercano a dar evidencia de que IMPLICIT_SAT en el caso promedio es casi tan rápidamente decidible como SAT en el peor de los casos. Pero no sé cómo se podría comparar directamente su noción con los lenguajes implícitos porque la noción de "circuito más pequeño para

I M P L I C I T_S A T = {circuits C : C implicitly specifies w, w \in S A T} .

$\mathsf{IMPLICIT\_SAT} = \{ \text{circuits $C$}: \text{$C$ implicitly specifies $w$}, w \in \mathsf{SAT}\}.$

w

$w$

w

$w$

f_{n}^{C} = Θ (f_{n})

$f^C_n = \Theta(f_n)$

w

$w$ "no entra en juego para lenguajes implícitos.

Espero que esto sea útil / interesante!

No estoy seguro de un libro de texto que mencione problemas implícitos, pero aquí hay algunas notas de la conferencia: http://people.seas.harvard.edu/~salil/cs221/spring10/lec8.pdf

usul
fuente

| J^{K} (n) | = 2^{n}

$\left|J^K(n)\right| = 2^n$ ? Pero no todas las descripciones son mínimas.

Andrew

@AndrewMacFie, correcto, debería ser "como mucho". Arreglará.

usul

Gracias por agregar esta respuesta :) Parece que para cualquier algoritmo para 3-SAT, va a crecer rápidamente.

f_{n}^{K}

$f^K_n$

Andrew

Un caso fácil parece ser donde el lenguaje contiene solo instancias rellenadas. Cuando se obtiene de un lenguaje rellenando cada instancia de tamaño con símbolos, puede estar en la región de . $S$ $S$ $L$ $n$ $2^n-n$ $f^K_{n}$ $2^{f_n}$

András Salamon
fuente

Tenga en cuenta que la respuesta de Yury subsume esta, y también hace precisa la "puede estar en la región de".

András Salamon