Circuito límites inferiores y complejidad kolmogorov

Considere el siguiente razonamiento:

Deje que denote la complejidad de Kolmogorov de la cadena . El teorema de incompletitud de Chaitin dice que $K(x)$ $x$

para cualquier sistema coherente y suficientemente fuerte formales , existe una constante (dependiendo sólo del sistema formal y su lenguaje) tal que para cualquier cadena , no puede demostrar que . $S$ $T$ $x$ $S$ $K(x) \geq T$

Sea una función booleana en variables, la complejidad de Kolmogorov de su espectro es como máximo . Supongamos que sea la complejidad del circuito de , es decir, el tamaño del circuito mínimo que computa . $f_n$ $n$ $k$ $S(f_n)$ $f_n$ $f_n$

Un límite superior (aproximado) para es para una constante y es una función de castor ocupado (los pasos máximos posibles a detener la máquina de Turing con una descripción del tamaño puede realizar). (Por cada en el espectro, construya el término mínimo de la asignación de verdad correspondiente y tome OR de todos estos términos mínimos juntos). $S(f_n)$

S (f_{n}) \leq c \cdot B B (k) \cdot n

$S(f_n)\leq c\cdot BB(k) \cdot n$

c

$c$

B B (k)

$BB(k)$

k

$k$

1

$1$

Supongamos ahora que para una familia infinita de funciones booleanas , tenemos una prueba formal de que requiere circuitos de tamaño superlineal, es decir $L = \{f_n\}_{n}$ $L$

donde .

S ⊢ \forall n \geq n_{0}, g (n) \cdot n \leq S (f_{n})

$S \vdash \forall n \geq n_0, \ g(n)\cdot n \leq S(f_n)$

g (n) \in ω (1)

$g(n)\in \omega(1)$

Si consideramos que es suficientemente grande, tendremos $n$

g (n) > c \cdot B B (T)

$g(n) > c\cdot BB(T)$

En particular, esto sería una prueba de que la complejidad de Kolmogorov del espectro de es al menos , lo cual es imposible. $f_n$ $T$

Esto lleva a dos preguntas:

1) Debería haber algo mal en el razonamiento anterior. Principalmente porque haría que los límites inferiores del circuito superlineal no fueran demostrables formalmente.

2) ¿Conocen enfoques similares para mostrar barreras para los límites inferiores, es decir, que muestran que ciertos tipos de límites inferiores (de circuito) son formalmente no demostrables?

cc.complexity-theory reference-request lo.logic circuit-complexity kolmogorov-complexity Magnus Find
fuente

Ideas interesantes algo relacionado con la prueba razborov / rudich re "pruebas naturales" que esboza las barreras para P =? NP (pero probablemente también aplicable a otras separaciones de clase de complejidad como se enumeran como ejemplos en el documento) ... ¿ha leído ese documento? ver también barreras P =? NP y barreras / complejidad de circuito monótono . aparentemente insinúa que las separaciones de clase de complejidad son similares en estructura a las pruebas de no demostrabilidad.

vzn

¿Puedes elaborar sobre el "espectro" de f_n? ¿Hay alguna manera de formular la pregunta sin referirse al "espectro"?

vzn

Probablemente sea cierto que uno puede estudiar la complejidad de las funciones al estudiar la TM más pequeña [en el sentido de la tabla / estados de estado] que las computa y que esto coincidirá aproximadamente con los límites inferiores del circuito. Si puede demostrar que es imposible, en lugar de realmente difícil, encontrar la TM más pequeña, es posible que tenga algo allí. sin embargo, es "simple" encontrar la TM más pequeña a través de una enumeración canónica de circuitos o TM. Si reflexiona sobre por qué funciona este enfoque, podría ser útil comprender por qué la pregunta no conduce a un problema.

vzn

(f (0, 0, . ., 0), f (0, 0, . ., 1), . ., f (1, 1, . ., 1))

$(f(0,0,..,0),f(0,0,..,1),..,f(1,1,..,1))$

$A(k)$ $K(A(k)) \geq k$ $k$ $K(A(k)) \geq k$

$BB(T)$

$\alpha(k)$ $k$ $\alpha(k)$ $K(0^{\alpha(k)+1}) > k$

Yuval Filmus
fuente

¿Por qué es problemática esta situación? No proporcionó un programa cuya salida sería A (k) y su longitud sería menor que k.

domotorp

B B (k)

$BB(k)$

k

$k$

Es problemático (posiblemente) en el mismo sentido que la pregunta original.

Yuval Filmus

Aún no lo entiendo. No exhibe una cadena y una prueba de que su complejidad de Kolmogorov es grande. Exhibe una prueba de que existe una cadena cuya complejidad es grande.

Sasho Nikolov

Creo que son problemáticos de diferentes maneras. Mientras lo leo, usted señala una afirmación verdadera específica, que no tiene una prueba. Al exponerlo en mi pregunta, señalo que eso implica una prueba de algo que no es demostrable.

Magnus Encuentra el

Circuito límites inferiores y complejidad kolmogorov

Respuestas: