Relación entre complejidad computacional e información

Trabajo en un laboratorio de neurociencia computacional que cuantifica la información mutua entre pares o grupos de neuronas. Recientemente, el jefe cambió su enfoque para medir la "complejidad de la dinámica neuronal". Al seguir esa línea de investigación, algunas personas en mi grupo parecen equiparar "complejo" con "tiene una alta entropía".

¿Alguien puede guiarme sobre cuál es la relación entre la complejidad computacional (en un sentido CS) y la entropía en el sentido de la teoría de la información?

Para explicar un poco más, las medidas como la complejidad de Lempel-Ziv no me parecen medidas válidas de complejidad porque combinan información (para el usuario) con la carga de muchos bits. Otras medidas, como [Causal State Splitting Reconstruction][1]son mucho menos conocidas, pero tienen la propiedad atractiva de que los procesos aleatorios tienen cero complejidad, porque se necesitan cero estados ocultos para representar un proceso aleatorio estacionario.

Hay suficientes conexiones entre la teoría de la información y la complejidad computacional para merecer un curso de posgrado, por ejemplo, este: http://www.cs.princeton.edu/courses/archive/fall11/cos597D/

Muchas personas han mencionado la complejidad de Kolmogorov o sus variantes limitadas por los recursos, pero creo que algo más cercano a lo que estás buscando es la noción de profundidad (lógica) . Hay varias variantes en profundidad, pero todas intentan llegar a algo como lo que estás hablando. En particular, ni las cadenas puramente aleatorias ni las cadenas muy ordenadas / repetitivas son profundas.

Una noción de profundidad es intuitivamente: una cadena es profunda si tiene una descripción corta, pero la única forma de reconstruir la cadena a partir de esa breve descripción lleva una cantidad de tiempo excesiva. Esta es la noción de profundidad y muchas otras se introducen y desarrollan en [1]. La otra referencia estándar es [2]. Los miraría, luego haría una búsqueda de referencia hacia adelante.

[1] L. Antunes, L. Fortnow, D. van Melkebeek, NV Vinodchandran. Profundidad computacional: concepto y aplicaciones . Theoret Comp. Sci. 354 (3): 391-404. También disponible gratuitamente en la página web del autor .

[2] CH Bennett. Profundidad lógica y complejidad física. En R. Herken (Ed.), The Universal Turing Machine: A Half-Century Survey, Oxford University Press, Oxford (1988), 227-257.

Lo primero que le viene a la mente como algo que puede encontrar fascinante es la complejidad de Kolmogorov; Ciertamente lo encuentro fascinante, y como no lo mencionaste, pensé que valdría la pena mencionarlo.

Dicho esto, un enfoque más general para responder a esta pregunta podría basarse en la teoría de los lenguajes y los autómatas. Los autómatas finitos deterministas son procesadores de cadena O (n). Es decir, dada una cadena de longitud n, procesan la cadena en n pasos precisos (mucho de esto depende precisamente de cómo defina autómatas finitos deterministas; sin embargo, un DFA ciertamente no requiere más pasos). Los autómatas finitos no deterministas reconocen los mismos lenguajes (conjuntos de cadenas) que los DFA y pueden transformarse en DFA, pero para simular un NFA en una máquina secuencial y determinista, normalmente debe explorar un "espacio de búsqueda" similar a un árbol que puede aumentar el complejidad dramáticamente. Los lenguajes regulares no son muy "complejos" en sentido computacional,

De manera similar, puede observar otros niveles de la jerarquía de idiomas de Chomsky: libre de contexto determinista, libre de contexto (incluidos los lenguajes libres de contexto no deterministas, que no necesariamente pueden ser reconocidos por autómatas deterministas), los lenguajes sensibles al contexto, los recursivos y los recursivos. idiomas enumerables, y los idiomas indecidibles.

Diferentes autómatas difieren principalmente en su almacenamiento externo; es decir, qué almacenamiento externo es necesario para que los autómatas procesen correctamente los idiomas de cierto tipo. Los autómatas finitos no tienen almacenamiento externo; Los PDA tienen una pila, y las máquinas de Turing tienen una cinta. Por lo tanto, podría interpretar que la complejidad de un problema de programación particular (que corresponde a un lenguaje) está relacionado con la cantidad o tipo de almacenamiento requerido para reconocerlo. Si no necesita o una cantidad fija y finita de almacenamiento para reconocer todas las cadenas en un idioma, es un idioma normal. Si todo lo que necesita es una pila, tiene un lenguaje sin contexto. Etc.

En general, no me sorprendería si los idiomas más altos en la jerarquía de Chomsky (por lo tanto, con mayor complejidad) también tienden a tener una mayor entropía en el sentido teórico de la información. Dicho esto, probablemente puedas encontrar muchos contraejemplos de esta idea, y no tengo idea de si tiene algún mérito.

Además, esto podría preguntarse mejor en el "cs teórico" (cstheory) StackExchange.

La complejidad computacional aborda los recursos necesarios: dado un tipo particular de problema, de cierto tamaño, cuáles son los recursos necesarios (generalmente tiempo, espacio o ambos; y un tipo particular de dispositivo informático) para resolverlo. Los problemas se agrupan en "clases" complejas.

Algunos de estos son bastante generales y abstractos: ¿es el problema solucionable, incluso en principio? ¿Requiere una máquina de este tipo o aquella? La introducción a estas ideas sigue siendo un tema de ciencias de la computación de nivel de posgrado, y el material de introducción generalmente hace referencia a la jerarquía de Chomsky, que mapea de manera clara (¡y hermosa!) Algunos tipos de máquinas abstractas y algunos tipos de resúmenes, Especificaciones del lenguaje matemático.

Algunos de estos, en el nivel inferior, son más prácticos en el uso diario: ¿Este problema se escala como el cuadrado del tamaño del problema, o el cubo, o alguna otra función? Curiosamente, sé que los argumentos sobre la entropía de un problema dado se han encontrado útiles para determinar algunos límites inferiores a algunos problemas computacionales. Uno que se me ocurre (aunque probablemente no podría repetirlo sin consultar un libro de texto) es un argumento basado en la entropía para el número mínimo necesario de comparaciones durante una clasificación. La conexión con la entropía es a través de la teoría de la información.

Entonces, hay algo de mérito en la idea, creo.