QUANDO UM 1 CUSTA MAIS QUE UM 0, A COMPRESSÃO FICA DIFÍCIL

Para armazenar ou enviar um texto de forma compacta, dê a cada símbolo uma palavra feita de 0s e 1s, curta para os símbolos frequentes e mais longa para os raros. As palavras devem formar um código de prefixo (prefix code): nenhuma palavra pode ser o começo de outra. {0, 10, 11} funciona; {0, 01, 11} não, já que 0 inicia 01. Com um código de prefixo, uma longa sequência de bits pode ser cortada de volta em palavras sem nenhum separador.

O melhor código desse tipo — o de menor comprimento médio — foi encontrado em 1952 por D. A. Huffman, com uma receita gulosa simples que roda rápido.

Quando as letras têm preço

A receita de Huffman supõe que um 0 e um 1 custam o mesmo. Suponha que não: o 1 leva mais tempo para ser transmitido, ou ocupa mais espaço para ser armazenado. Agora cada palavra custa a soma de suas letras, e a composição de uma palavra importa tanto quanto seu comprimento. Com custos 1 e 3, por exemplo, 00 e 01 têm o mesmo comprimento, mas custam 2 e 4.

Essa variante tem uma longa história. R. M. Karp a formulou como um problema de programação inteira em 1961. Trabalhos posteriores encontraram algoritmos exatos e eficientes para qualquer par fixo de custos inteiros, e um esquema de aproximação que chega tão perto do ótimo quanto se queira. Mas, quando os próprios custos fazem parte da entrada, ninguém sabia quão difícil era o problema. Ainda em 2021, ele constava como aberto.

A resposta: NP-completo

L. Sunil Chandran, do Indian Institute of Science, em Bengaluru, e Rishikesh Gajjala, da Pramaana Labs, provam agora que decidir se existe um código de custo no máximo K é NP-completo — mesmo quando os dois custos são inteiros consecutivos, M e M + 1. Os cientistas da computação chamam um problema de NP-completo quando ele é tão difícil quanto toda uma família de problemas clássicos: um método geral rápido para um deles daria um para todos, e nenhum é conhecido. Encontrar o código mais barato é, portanto, NP-difícil.

Não há contradição com os algoritmos rápidos para custos fixos. Na prova, M cresce com a entrada; para qualquer par de custos fixado de antemão, esses algoritmos continuam valendo.

Um quebra-cabeça escondido numa árvore de codificação

A prova parte de um problema difícil conhecido: numa rede desenhada numa folha sem cruzamentos, é possível escolher k pontos sem que dois deles estejam ligados? Ela então constrói um problema de codificação cujo código mais barato responde a essa pergunta.

1. Todo código de prefixo é uma árvore: 0 vai para a esquerda, 1 vai para a direita. Uma palavra de profundidade d com z uns custa M × d + z quando as letras custam M e M + 1. A profundidade define a parte grande do custo, e o número de 1s, a parte pequena.
2. Os autores concebem um novo problema intermediário: fixar quantas folhas a árvore tem em cada profundidade e dar uma pontuação à posição de suas folhas. Eles mostram que uma árvore barata precisa, enquanto cresce nível a nível, executar um pequeno programa que verifica os pontos escolhidos um a um, copia cada escolha e testa cada ligação. Qualquer atalho custa pelo menos uma unidade a mais; cada ponto escolhido economiza exatamente uma.
3. Por fim, as frequências são ajustadas para que cada símbolo seja forçado à profundidade certa, e a pontuação passa a ser o custo de codificação mais uma quantidade fixa.

Um pequeno exemplo do artigo mostra como os custos são sutis. Três símbolos têm frequências 20, 12 e 9, e as letras custam 83 e 84. O código (0, 10, 11) custa 5.176. O código (1, 00, 01) custa 5.175: dar a letra cara ao símbolo mais frequente compensa, porque as duas outras palavras passam a carregar menos 1s.

Onde a dificuldade se esconde

Um segundo resultado localiza o problema dentro da codificação comum. A receita de Huffman encontra rapidamente o menor comprimento médio. Mas, entre todos os códigos que atingem esse comprimento, escolher aquele com menos 1s, ponderados pela frequência, também é NP-completo.

Restam perguntas: se o problema continua difícil quando todos os números são pequenos (a chamada NP-dificuldade forte), e se um esquema rápido consegue aproximar o ótimo com qualquer precisão, com um tempo de execução que também cresça de forma razoável com essa precisão.

Uma prova encontrada com uma IA

O artigo declara como ela foi obtida. Os autores primeiro pediram ao Codex, da OpenAI, uma prova de dificuldade para um problema mais geral, depois pediram que a estendesse a códigos não binários e, por fim, a códigos binários. O Codex contribuiu para a estratégia da redução e para seu desenvolvimento matemático; também ajudou na redação, na verificação de argumentos e na construção de exemplos. Os autores orientaram o trabalho, pediram correções e simplificações, reescreveram substancialmente a exposição e assumem a responsabilidade pelos enunciados e provas finais. Como todo preprint, ainda não passou por revisão por pares.