arXiv · Oct 15, 2026
The Information Bottleneck is NP-hard
By Bruno R, Vaccaro U
Given a joint distribution PXY on a finite alphabet, the information bottleneck method seeks a representation T of X that is as informative as possible about Y while compressing X, where T and Y are conditionally independent given X. We show that computing the optimal value IB(PXY,R) = supT \ I(Y;T) : I(X;T) ≤ R \ of the information bottleneck problem, as well as its Lagrangian relaxation Lβ(PXY) = supT [I(Y;T) - β I(X;T)], is NP-hard. Moreover, unless P = NP, neither IB(PXY,R) nor Lβ(PXY) can be approximated in polynomial time within an additive error of order |X|^(-3/2).