Zero-error instantaneous coding of correlated sources with length constraints is NP-complete
Ying-On Yan, T. Berger · IEEE Transactions on Information Theory · 2006
It is well known that the Kraft inequality gives a necessary and sufficient condition on the codeword lengths of a zero-error instantaneous code for a single source. However, generalization for two correlated sources is nontrivial. We show that in the Slepian-Wolf configuration, even if one source is known at the decoder, designing a zero-error instantaneous code with given codeword lengths for the other source is NP-complete.