Pay for your letters

1 · Say what the paper proves

Beginner

What do Chandran and Gajjala prove?

Finding the cheapest prefix code is NP-hard when the letter costs are part of the input Huffman's recipe gives bad codes when 0 and 1 cost the same No fast algorithm exists even when the costs are fixed in advance

2 · Find the cheapest code

Three symbols with frequencies 20, 12 and 9. The letter 0 costs 83, the letter 1 costs 84. Each word costs the sum of its letters, multiplied by the frequency of its symbol.

Intermediate

Which code is the cheapest?

(0, 10, 11) (10, 0, 11) (1, 00, 01)

3 · Reconcile the two results

For every fixed pair of integer costs, for instance 1 and 2, an exact and fast algorithm already exists.

Expert

Why does the NP-completeness proof not contradict this?

Because those fast algorithms are wrong Because, in the proof, M grows with the input Because the proof uses only equal frequencies

4 · Locate the difficulty

Huffman's recipe quickly finds the minimum weighted length of a code.

Expert

According to the paper, what remains NP-complete?

Choosing, among the codes of that minimum length, the one with the fewest weighted 1s Computing that minimum length itself Checking that a given code reaches a claimed cost

Letters paid for

—