← 研踪 PaperTrailarXiv:2611.04444 · v1
Binary Huffman Coding with Unequal Letter Costs Is NP-Complete
首次提交 2026-11-03 15:36
版本更新 2026-11-03 15:36
雷达观测 2026-11-04 23:40
摘要
Binary prefix coding assigns prefix-free binary words to symbols to minimize their frequency-weighted cost. Huffman solved the equal-letter-cost case in polynomial time in 1952 [Proc. IRE'52]. For unequal letter costs, Karp gave an integer-programming formulation in 1961 [IRE Trans. Inf. Theory'61]. Exact polynomial-time algorithms for fixed integer costs were given by Golin and Rote [IEEE Trans. Inf. Theory'98] and Bradford, Golin, Larmore, and Rytter [J. Algorithms'02]. For input-dependent costs, Golin, Mathieu, and Young gave a polynomial-time approximation scheme [SICOMP'12]. The exact complexity when letter costs are part of the input had remained unresolved. We resolve this $65$-year-old problem by proving that deciding whether there exists a binary prefix-free code of frequency-weighted cost at most a given threshold is NP-complete, even when the letter costs are consecutive positive integers $(M,M+1)$ supplied as part of the input. All frequencies, letter costs, and thresholds are encoded in binary. Consequently, finding an optimal code is NP-hard. Our proof uses two polynomial-time reductions, starting from Planar Independent Set. The intermediate problem prescribes the number of leaves at each depth of a full ordered binary tree and minimizes a signed linear score on their sorted right-edge counts. The first reduction represents an independent-set verification program by a tree growing level by level. A fixed-profile identity converts narrow coordinate restrictions into linear penalties that enforce the computation. The second reduction adds large dyadic terms to the symbol frequencies to force prescribed depths. These terms contribute a constant to the weighted number of ones, leaving smaller signed perturbations to reproduce the tree score.
作者备注：51 pages
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-03 15:36 · 最新观测版本
Binary Huffman Coding with Unequal Letter Costs Is NP-Complete
Binary prefix coding assigns prefix-free binary words to symbols to minimize their frequency-weighted cost. Huffman solved the equal-letter-cost case in polynomial time in 1952 [Proc. IRE'52]. For unequal letter costs, Karp gave an integer-programming formulation in 1961 [IRE Trans. Inf. Theory'61]. Exact polynomial-time algorithms for fixed integer costs were given by Golin and Rote [IEEE Trans. Inf. Theory'98] and Bradford, Golin, Larmore, and Rytter [J. Algorithms'02]. For input-dependent costs, Golin, Mathieu, and Young gave a polynomial-time approximation scheme [SICOMP'12]. The exact complexity when letter costs are part of the input had remained unresolved. We resolve this $65$-year-old problem by proving that deciding whether there exists a binary prefix-free code of frequency-weighted cost at most a given threshold is NP-complete, even when the letter costs are consecutive positive integers $(M,M+1)$ supplied as part of the input. All frequencies, letter costs, and thresholds are encoded in binary. Consequently, finding an optimal code is NP-hard. Our proof uses two polynomial-time reductions, starting from Planar Independent Set. The intermediate problem prescribes the number of leaves at each depth of a full ordered binary tree and minimizes a signed linear score on their sorted right-edge counts. The first reduction represents an independent-set verification program by a tree growing level by level. A fixed-profile identity converts narrow coordinate restrictions into linear penalties that enforce the computation. The second reduction adds large dyadic terms to the symbol frequencies to force prescribed depths. These terms contribute a constant to the weighted number of ones, leaving smaller signed perturbations to reproduce the tree score.
查看此版本解读 →查看此版本原文 ↗