WHEN A 1 COSTS MORE THAN A 0, COMPRESSION GETS HARD

To store or send a text compactly, give each symbol a word made of 0s and 1s, short for frequent symbols and longer for rare ones. The words must form a prefix code: no word may be the beginning of another. {0, 10, 11} works; {0, 01, 11} does not, since 0 starts 01. With a prefix code, a long string of bits can be cut back into words without any separator.

The best such code — the one with the smallest average length — was found in 1952 by D. A. Huffman, with a simple greedy recipe — one that makes the best-looking choice at each step — that runs fast.

When letters have a price

Huffman’s recipe assumes that a 0 and a 1 cost the same. Suppose they do not: the 1 takes longer to transmit, or more room to store. Now each word costs the sum of its letters, and the composition of a word matters as much as its length. With costs 1 and 3, for instance, 00 and 01 are equally long but cost 2 and 4.

This variant has a long history. R. M. Karp wrote it as an integer-programming problem — an optimization whose unknowns must be whole numbers — in 1961. Later work found exact, efficient algorithms for any fixed pair of integer costs, and an approximation scheme that comes as close to the optimum as desired. But when the costs themselves are part of the input, nobody knew how hard the problem was. As late as 2021, it was still listed as open.

The answer: NP-complete

L. Sunil Chandran, of the Indian Institute of Science in Bengaluru, and Rishikesh Gajjala, of Pramaana Labs, now prove that deciding whether a code of cost at most K exists is NP-complete — even when the two costs are consecutive integers, M and M + 1. Computer scientists call a problem NP-complete when it is as hard as a whole family of classic problems: a fast general method for one would give one for all, and none is known. Finding the cheapest code, which would answer that yes-or-no question at once, is therefore at least as hard — NP-hard, in the jargon.

There is no contradiction with the fast algorithms for fixed costs. In the proof, M grows with the input; for any pair of costs fixed in advance, those algorithms still apply.

A puzzle hidden in a coding tree

The proof starts from a known hard problem: in a network drawn on a sheet without crossings, can you pick k points with no two of them linked? It then builds a coding problem whose cheapest code answers that question.

1. Any prefix code is a tree: 0 goes left, 1 goes right, and each word is a leaf, the end of a branch. A word of depth d — that is, of d letters — with z ones costs M × d + z when the letters cost M and M + 1. The depth sets the big part of the cost, and the number of 1s the small part.
2. The authors design a new intermediate problem: fix how many leaves the tree has at each depth, and score where its leaves sit. They show that a cheap tree must, as it grows level by level, run a small program that checks the chosen points one by one, copies each choice and tests every link. Any deviation from that program costs at least one unit more; each point chosen saves exactly one.
3. Finally, frequencies are tuned so that each symbol is forced to the right depth, and the score becomes the coding cost plus a fixed amount.

A small example from the paper shows how subtle the costs are. Three symbols have frequencies 20, 12 and 9; the 0 costs 83 and the 1 costs 84. The code (0, 10, 11) — 0 for the most frequent symbol, 10 and 11 for the other two — costs 5,176. The code (1, 00, 01) costs 5,175: giving the expensive letter to the most frequent symbol wins, because the two other words then carry fewer 1s.

Where the difficulty hides

A second result locates the trouble inside ordinary coding. Huffman’s recipe finds the shortest average length quickly. But among all the codes that reach that length, picking the one with the fewest 1s, weighted by frequency, is NP-complete too.

Questions remain: whether the problem stays hard when all numbers are small (so-called strong NP-hardness), and whether a fast scheme can approximate the optimum to any precision with a running time that also grows reasonably with that precision.

A proof found with an AI

The paper states how it was obtained. The authors first asked OpenAI’s Codex for a hardness proof of a more general problem, then asked it to extend it to nonbinary and finally to binary codes. Codex contributed to the strategy of the reduction (the translation of the network puzzle into a coding problem) and its mathematical development; it also helped with drafting, checking arguments and building examples. The authors guided the work, requested corrections and simplifications, substantially rewrote the exposition, and take responsibility for the final statements and proofs. Like any preprint, it has not yet been peer-reviewed.