The complexity of the generalized Lloyd - Max problem (Corresp.)
Michael R. Garey, David S. Johnson, Hans S. Witsenhausen · IEEE Transactions on Information Theory · 1982
A simple (combinatorial) special case of the generalized Lloyd-Max (or quantization) problem is shown to be nondeterministic polynomial (NP)-complete. {\em A fortiori}, the general problem of communication theory, in its combinatorial forms, has at least that complexity.