Optimal Mutual Information Quantization is NP-complete

Optimal Mutual Information Quantization is NP-complete Brendan Mumey, Department of Computer Science, Montana State University

We consider the computational complexity of quantizing a joint $(X,Y)$ probability distribution in order to maximize the mutual information of the quantization. We show that, in general, this problem is NP-complete via reductions from various forms of the PARTITION problem.