Compresión de entropía

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 el historial 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 este registro, y de modo que la cantidad de información adicional registrada en cada paso del proceso sea (en promedio) menor que la cantidad de información nueva generada aleatoriamente en cada paso. La discrepancia creciente resultante en el contenido total de información nunca puede exceder la cantidad fija de información en el estado actual, de lo cual 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 ser parametrizados por dos números${\displaystyle (k,t)}$dónde${\displaystyle k}$es el número de variables por cláusula y${\displaystyle t}$es el número máximo de cláusulas diferentes en las que puede aparecer cualquier variable. Si las variables se asignan aleatoriamente como verdaderas o falsas, entonces el evento de que una cláusula no se cumpla ocurre con probabilidad${\displaystyle 2^{-k}}$y cada evento es independiente de todos excepto${\displaystyle r=k(t-1)}$otros eventos. Del lema local de Lovász se deduce que, si${\displaystyle t}$es lo suficientemente pequeño como para hacerlo${\displaystyle r<2^{k}/e}$(dónde${\displaystyle e}$es la base del logaritmo natural ) entonces siempre existe una solución. El siguiente algoritmo se puede mostrar utilizando compresión de entropía para encontrar dicha solución para entradas que cumplen una restricción en${\displaystyle r}$de forma similar.

• Elija una asignación de verdad al azar
• Mientras exista una cláusula insatisfecha${\displaystyle C}$, llamar a una subrutina recursiva fixcon${\displaystyle C}$como su argumento. Esta subrutina elige una nueva asignación de verdad aleatoria para las variables en${\displaystyle C}$y luego llama recursivamente a la misma subrutina en todas las cláusulas no satisfechas (posiblemente incluyendo${\displaystyle C}$sí mismo) que comparten una variable con${\displaystyle C}$, hasta que no quede ninguno.

Este algoritmo no puede terminar a menos que la fórmula de entrada sea satisfacible, por lo que una prueba de que termina también es una prueba de que existe una solución. Cada iteración del bucle externo reduce el número de cláusulas insatisfechas (provoca${\displaystyle C}$para quedar satisfecho sin que ninguna otra cláusula quede insatisfecha), por lo que la pregunta clave es si la fixsubrutina termina o si puede entrar en una recursión infinita . ^{[ 3 ]}

Para responder a esta pregunta, consideremos por un lado el número de bits aleatorios generados en cada iteración de la fixsubrutina (${\displaystyle 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 (${\displaystyle n}$bits), la secuencia de argumentos a las llamadas más externas a la fixsubrutina (como máximo)${\displaystyle m\log _{2}m}$bits, donde${\displaystyle m}$es el número de cláusulas en la entrada), y luego una secuencia de registros que indican que una llamada recursiva devolvió fixo que realizó una llamada recursiva, y cuál de las${\displaystyle r+1}$Las cláusulas que comparten una variable con la cláusula actual se pasaron como argumento a esa llamada recursiva. Hay${\displaystyle r+2}$posibles resultados por registro, por lo que el número de bits necesarios para almacenar un registro (utilizando un método de codificación compacto como la codificación aritmética que permite el almacenamiento utilizando un número fraccional de bits por registro) es${\displaystyle \log _{2}(r+2)}$. ^{[ 3 ]}

Esta información es suficiente para recuperar toda la secuencia de llamadas a fix, incluyendo la identidad de la cláusula dada como argumento a cada llamada. Para ello, avance a través de la secuencia de llamadas utilizando los argumentos de llamada más externos almacenados y los registros almacenados para inferir el argumento de cada llamada a su vez. Una vez recuperada la secuencia de llamadas recursivas y sus argumentos, las asignaciones de verdad en cada etapa de este proceso también pueden recuperarse a partir de la misma información. Para ello, comience desde la asignación de verdad final y luego avance hacia atrás a través de la secuencia de cláusulas reasignadas aleatoriamente, utilizando el hecho de que cada cláusula era previamente insatisfacible para determinar de forma única los valores de todas sus variables antes de su reasignación aleatoria. Por lo tanto, después${\displaystyle f}$llamadas a fix, el algoritmo habrá generado${\displaystyle fk}$bits aleatorios pero todo su historial (incluidos esos bits generados) se puede recuperar de un registro que utiliza solo${\displaystyle m\log _{2}m+n+f\log _{2}(r+2)}$bits. Esto solo es posible cuando el número de bits almacenados es al menos tan grande como el número de bits generados aleatoriamente. De ello se deduce que, cuando${\displaystyle r}$es lo suficientemente pequeño como para hacerlo${\displaystyle \log _{2}(r+2)<k}$, es decir, cuando${\displaystyle r<2^{k}-2}$, la fixsubrutina solo puede realizar${\displaystyle O(m\log _{2}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 para él por otros investigadores. ^{[ 5 ] [ 6 ] [ 7 ]}

La versión original de Moser del lema local algorítmico de Lovász , utilizando este método, obtuvo cotas más débiles que el lema local de Lovász original , que fue formulado originalmente como un teorema de existencia sin un método constructivo para encontrar el objeto cuya existencia demuestra. Posteriormente, Moser y Gábor Tardos utilizaron el mismo método para demostrar una versión del lema local algorítmico de Lovász que iguala las cotas 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 proporcionaría el lema local de Lovász. Por ejemplo, para el problema de la coloración acíclica de aristas de grafos con grado máximo${\displaystyle \Delta }$, se demostró por primera vez utilizando el lema local que siempre existe una coloración con${\displaystyle 64\Delta }$colores, y más tarde usando una versión más fuerte del lema local esto se mejoró a${\displaystyle 9.62\Delta }$Sin embargo, un argumento más directo que utiliza la compresión de entropía muestra que existe una coloración que utiliza únicamente${\displaystyle 4\Delta -4}$colores, y además esta coloración se puede encontrar en tiempo polinomial aleatorio. ^{[ 6 ]}