En matemáticas y ciencias de la computación teórica, la compresión de entropía es un método de teoría de la información para demostrar que un proceso aleatorio termina, utilizado originalmente por Robin Moser para demostrar una versión algorítmica del lema local de Lovász . [1] [2]
Para utilizar este método, se demuestra que la historia del proceso dado puede registrarse de manera eficiente, de modo que el estado del proceso en cualquier momento pasado pueda recuperarse a partir del estado actual y de este registro, y de modo que la cantidad de información adicional que se registra en cada paso del proceso sea (en promedio) menor que la cantidad de información nueva generada aleatoriamente en cada paso. La creciente discrepancia resultante en el contenido total de información nunca puede exceder la cantidad fija de información en el estado actual, de lo que se deduce que el proceso debe terminar eventualmente. Este principio puede formalizarse y hacerse riguroso utilizando la complejidad de Kolmogorov . [3]
Un ejemplo dado tanto por Fortnow [3] como por Tao [4] se refiere al problema de satisfacibilidad booleana para fórmulas booleanas en forma normal conjuntiva , con tamaño de cláusula uniforme. Estos problemas pueden parametrizarse mediante dos números ( k , t ) donde k es el número de variables por cláusula y t es el número máximo de cláusulas diferentes en las que puede aparecer cualquier variable. Si las variables se asignan como verdaderas o falsas aleatoriamente, entonces el evento de que una cláusula no se satisfaga ocurre con una probabilidad de 2 − k y cada evento es independiente de todos los demás eventos excepto r = k ( t − 1). Del lema local de Lovász se deduce que, si t es lo suficientemente pequeño como para hacer que r < 2 k / e (donde e es la base del logaritmo natural ), entonces siempre existe una solución. El siguiente algoritmo se puede mostrar utilizando la compresión de entropía para encontrar dicha solución cuando r es menor por un factor constante que este límite:
Este algoritmo no puede terminar a menos que la fórmula de entrada sea satisfactoria, por lo que una prueba de que termina es también una prueba de que existe una solución. Cada iteración del bucle externo reduce el número de cláusulas insatisfechas (hace que C se satisfaga sin hacer que ninguna otra cláusula se vuelva insatisfecha), por lo que la pregunta clave es si la subrutina fix termina o si puede entrar en una recursión infinita . [3]
Para responder a esta pregunta, considere por un lado el número de bits aleatorios generados en cada iteración de la subrutina fix ( k bits por cláusula) y por otro lado el número de bits necesarios para registrar el historial de este algoritmo de tal manera que se pueda generar cualquier estado pasado. Para registrar este historial, podemos almacenar la asignación de verdad actual ( n bits), la secuencia de argumentos iniciales a la subrutina fix ( m log m bits, donde m es el número de cláusulas en la entrada), y luego una secuencia de registros que indican que una llamada recursiva a fix regresó o que a su vez hizo otra llamada a una de las r + 1 cláusulas (incluyendo C en sí) que comparten una variable con C . Hay r + 2 resultados posibles por registro, por lo que el número de bits necesarios para almacenar un registro es log r + O (1). [3]
Esta información se puede utilizar para recuperar la secuencia de cláusulas dadas como argumentos recursivos a fix . Las asignaciones de verdad en cada etapa de este proceso se pueden recuperar (sin tener que registrar ninguna información adicional) progresando hacia atrás a través de esta secuencia de cláusulas, utilizando el hecho de que cada cláusula era previamente insatisfactoria para inferir los valores de todas sus variables antes de cada llamada fix . Por lo tanto, después de f llamadas a fix , el algoritmo habrá generado fk bits aleatorios pero su historial completo (incluidos los bits generados) se puede recuperar de un registro que utiliza solo m log m + n + f log r + O ( f ) bits. De ello se deduce que, cuando r es lo suficientemente pequeño como para hacer log r + O (1) < k , la subrutina fix solo puede realizar O ( m log m + n ) llamadas recursivas a lo largo de todo el algoritmo. [3]
El nombre "compresión de entropía" fue dado a este método en una publicación de blog por Terence Tao [4] y desde entonces ha sido utilizado por otros investigadores. [5] [6] [7]
La versión original de Moser del lema local algorítmico de Lovász , que utiliza este método, logró límites más débiles que el lema local de Lovász original , que originalmente se formuló como un teorema de existencia sin un método constructivo para encontrar el objeto cuya existencia prueba. Más tarde, Moser y Gábor Tardos utilizaron el mismo método para probar una versión del lema local algorítmico de Lovász que coincide con los límites del lema original. [8]
Desde el descubrimiento del método de compresión de entropía, también se ha utilizado para lograr límites más fuertes para algunos problemas que los que se obtendrían con el lema local de Lovász. Por ejemplo, para el problema de la coloración acíclica de los bordes de los grafos con un grado máximo Δ, primero se demostró utilizando el lema local que siempre existe una coloración con 64 Δ colores, y más tarde, utilizando una versión más fuerte del lema local, esto se mejoró a 9,62 Δ. Sin embargo, un argumento más directo utilizando la compresión de entropía muestra que existe una coloración que utiliza solo 4(Δ − 1) colores, y además esta coloración se puede encontrar en tiempo polinomial aleatorio. [6]