Reproduce “Binary Huffman Coding with Unequal Letter Costs Is NP-Complete” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
L. Sunil Chandran, Rishikesh Gajjala
The authors prove exact binary prefix coding with unequal letter costs is computationally hard. They reduce Planar Independent Set through a tree-scoring problem, encoding graph choices as tree structure and then as code costs. The threshold decision problem is NP-complete even for consecutive costs (M, M+1), where M varies with the input and numbers are binary-encoded; this is not strong NP-hardness.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.