Given a joint distribution $P_{XY}$ of random variables $X,Y$ on finite alphabets, the information
bottleneck method seeks a representation $T$ of $X$ that is as informative as possible about $Y$ while compressing $X$; the privacy funnel asks for a representation that discloses much about $X$ while leaking little about $Y$. In both scenarios $T$ and $Y$ are conditionally independent given $X$. We show that computing the optimal value
$IB(P_{XY},R) = \sup_T \{ I(Y;T) : I(X;T) \le R \}$ of the
information bottleneck problem, as well as its Lagrangian relaxation
$L_\beta(P_{XY}) = \sup_T [ I(Y;T) - \beta I(X;T) ]$, is NP-hard.
Moreover, unless $\mathrm{P} = \mathrm{NP}$, neither $IB(P_{XY},R)$ nor $L_\beta(P_{XY})$ can be approximated in polynomial time within an
additive error of order $|\mathcal{X}|^{-(1+\alpha)}$, for every fixed $\alpha > 0$. We also prove that computing the privacy funnel
$PF(P_{XY},r) = \inf_T \{ I(Y;T) : I(X;T) \ge r \}$ and its Lagrangian relaxation $\Lambda_\beta(P_{XY}) = \inf_T [ I(Y;T) - \beta I(X;T) ]$ is
NP-hard, and that, unless $\mathrm{P} = \mathrm{NP}$, neither can be approximated in polynomial time within an additive error of order $|\mathcal{X}|^{-2}$.