当1比0更贵，压缩就变难了
要紧凑地存储或发送一段文本，可以给每个符号分配一个由0和1组成的码字，常见符号用短码字，罕见符号用长码字。这些码字必须构成前缀码：任何一个码字都不能是另一个码字的开头。{0, 10, 11}可行；{0, 01, 11}不行，因为0是01的开头。有了前缀码，一长串比特无需任何分隔符就能被重新切分成码字。
最优的这类编码——平均长度最小的那一种——由D. A. Huffman于1952年找到，用的是一种运行很快的简单贪心方法。
当字母有了价格
Huffman的方法假设0和1的代价相同。假设并非如此：1需要更长的传输时间，或者更多的存储空间。这样一来，每个码字的代价就是其各个字母代价之和，码字的组成与它的长度同样重要。例如，当代价为1和3时，00和01一样长，但代价分别是2和4。
这个变体有着悠久的历史。R. M. Karp在1961年把它写成了一个整数规划问题。后来的研究为任意一对固定的整数代价找到了精确而高效的算法，还找到了一种可以任意逼近最优值的近似方案。但当代价本身也是输入的一部分时，没有人知道这个问题有多难。直到2021年，它仍被列为未解决问题。
答案：NP完全
班加罗尔印度科学研究所的L. Sunil Chandran和Pramaana Labs的Rishikesh Gajjala现在证明，判定是否存在代价至多为K的编码是NP完全的——即使两个代价是相邻整数M和M + 1。计算机科学家把一个问题称为NP完全，是指它和一整类经典问题一样难：只要其中一个问题有快速的通用方法，所有问题就都有，而目前还不知道任何这样的方法。因此，寻找代价最低的编码是NP困难的。
这与固定代价下的快速算法并不矛盾。在证明中，M随输入增长；对于任何事先固定的一对代价，那些算法依然适用。
藏在编码树里的谜题
证明从一个已知的难题出发：在一张画在纸上、没有交叉的网络中，能否选出k个点，使其中任意两点都不相连？然后它构造出一个编码问题，其代价最低的编码就能回答这个问题。
- 任何前缀码都是一棵树：0向左，1向右。当字母代价为M和M + 1时，一个深度为d、含有z个1的码字的代价是M × d + z。深度决定代价的主要部分，1的个数决定较小的部分。
- 作者设计了一个新的中间问题：固定树在每个深度上的叶子数，并根据叶子所处的位置打分。他们证明，一棵代价低的树在逐层生长时，必须运行一个小程序：逐个检查被选中的点，复制每一次选择，并检验每一条连接。任何捷径都至少多花一个单位；每选中一个点恰好节省一个单位。
- 最后，通过调整频率，迫使每个符号处于正确的深度，于是分数就变成了编码代价加上一个固定值。
论文中的一个小例子展示了这些代价有多微妙。三个符号的频率分别为20、12和9，字母代价为83和84。编码(0, 10, 11)的代价是5,176。编码(1, 00, 01)的代价是5,175：把较贵的字母分给频率最高的符号反而更好，因为这样另外两个码字所含的1更少。
难点藏在哪里
第二个结果把麻烦定位在普通编码的内部。Huffman的方法能很快找到最短的平均长度。但在所有达到这一长度的编码中，挑出按频率加权后1的个数最少的那一个，同样是NP完全的。
仍有一些问题有待解答：当所有数字都很小时，这个问题是否依然困难（即所谓的强NP困难性）；以及是否存在一种快速方案，能以任意精度逼近最优值，且其运行时间随精度的增长也是合理的。
借助人工智能找到的证明
论文说明了证明是如何得到的。作者首先请OpenAI的Codex为一个更一般的问题给出困难性证明，然后让它把证明推广到非二元编码，最后推广到二元编码。Codex为归约的策略及其数学推导做出了贡献；它还协助了起草、检查论证和构造例子。作者引导了这项工作，要求修正和简化，大幅改写了论述，并对最终的命题和证明负责。和所有预印本一样，它尚未经过同行评审。