CUANDO UN 1 CUESTA MÁS QUE UN 0, COMPRIMIR SE VUELVE DIFÍCIL

Para almacenar o enviar un texto de forma compacta, se asigna a cada símbolo una palabra hecha de 0 y 1, corta para los símbolos frecuentes y más larga para los raros. Las palabras deben formar un código prefijo: ninguna palabra puede ser el comienzo de otra. {0, 10, 11} funciona; {0, 01, 11} no, porque 0 es el comienzo de 01. Con un código prefijo, una larga cadena de bits puede volver a cortarse en palabras sin ningún separador.

El mejor de estos códigos —el de menor longitud media— lo encontró en 1952 D. A. Huffman, con una receta voraz sencilla que se ejecuta rápido.

Cuando las letras tienen precio

La receta de Huffman supone que un 0 y un 1 cuestan lo mismo. Supongamos que no: el 1 tarda más en transmitirse, u ocupa más espacio al almacenarse. Ahora cada palabra cuesta la suma de sus letras, y la composición de una palabra importa tanto como su longitud. Con costes 1 y 3, por ejemplo, 00 y 01 son igual de largos, pero cuestan 2 y 4.

Esta variante tiene una larga historia. R. M. Karp la planteó como un problema de programación entera en 1961. Trabajos posteriores encontraron algoritmos exactos y eficientes para cualquier par fijo de costes enteros, y un esquema de aproximación que se acerca al óptimo tanto como se quiera. Pero cuando los propios costes forman parte de los datos de entrada, nadie sabía lo difícil que era el problema. Todavía en 2021 figuraba como abierto.

La respuesta: NP-completo

L. Sunil Chandran, del Instituto Indio de Ciencia (Indian Institute of Science) de Bengaluru, y Rishikesh Gajjala, de Pramaana Labs, demuestran ahora que decidir si existe un código de coste como máximo K es NP-completo, incluso cuando los dos costes son enteros consecutivos, M y M + 1. En informática se dice que un problema es NP-completo cuando es tan difícil como toda una familia de problemas clásicos: un método general rápido para uno daría uno para todos, y no se conoce ninguno. Encontrar el código más barato es, por tanto, NP-difícil.

No hay contradicción con los algoritmos rápidos para costes fijos. En la demostración, M crece con la entrada; para cualquier par de costes fijado de antemano, esos algoritmos siguen siendo válidos.

Un rompecabezas oculto en un árbol de codificación

La demostración parte de un problema difícil conocido: en una red dibujada sobre una hoja sin cruces, ¿se pueden elegir k puntos sin que haya dos unidos entre sí? Después construye un problema de codificación cuyo código más barato responde a esa pregunta.

1. Todo código prefijo es un árbol: el 0 va a la izquierda, el 1 a la derecha. Una palabra de profundidad d con z unos cuesta M × d + z cuando las letras cuestan M y M + 1. La profundidad fija la parte grande del coste, y el número de 1 la parte pequeña.
2. El equipo diseña un nuevo problema intermedio: fijar cuántas hojas tiene el árbol a cada profundidad y puntuar dónde se sitúan sus hojas. Demuestra que un árbol barato debe, a medida que crece nivel a nivel, ejecutar un pequeño programa que comprueba los puntos elegidos uno a uno, copia cada elección y verifica cada enlace. Cualquier atajo cuesta al menos una unidad más; cada punto elegido ahorra exactamente una.
3. Por último, las frecuencias se ajustan para que cada símbolo quede forzado a la profundidad correcta, y la puntuación pasa a ser el coste de codificación más una cantidad fija.

Un pequeño ejemplo del artículo muestra lo sutiles que son los costes. Tres símbolos tienen frecuencias 20, 12 y 9, y las letras cuestan 83 y 84. El código (0, 10, 11) cuesta 5.176. El código (1, 00, 01) cuesta 5.175: dar la letra cara al símbolo más frecuente sale ganando, porque las otras dos palabras llevan entonces menos 1.

Dónde se esconde la dificultad

Un segundo resultado sitúa el problema dentro de la codificación ordinaria. La receta de Huffman encuentra rápidamente la longitud media más corta. Pero, entre todos los códigos que alcanzan esa longitud, elegir el que tiene menos 1, ponderados por frecuencia, también es NP-completo.

Quedan preguntas abiertas: si el problema sigue siendo difícil cuando todos los números son pequeños (lo que se llama NP-dificultad fuerte), y si un esquema rápido puede aproximar el óptimo con cualquier precisión con un tiempo de ejecución que también crezca de forma razonable con esa precisión.

Una demostración hallada con una IA

El artículo explica cómo se obtuvo. El equipo pidió primero a Codex, de OpenAI, una demostración de dificultad para un problema más general, y luego que la extendiera a códigos no binarios y, por último, binarios. Codex contribuyó a la estrategia de la reducción y a su desarrollo matemático; también ayudó con la redacción, la comprobación de argumentos y la construcción de ejemplos. El equipo guio el trabajo, pidió correcciones y simplificaciones, reescribió a fondo la exposición y asume la responsabilidad de los enunciados y las demostraciones finales. Como cualquier prepublicación (preprint), aún no ha pasado la revisión por pares.