We investigate certain optimization problems for Shannon information
measures, namely, minimization of joint and conditional entropies $H(X,Y)$,
$H(X|Y)$, $H(Y|X)$, and maximization of mutual information $I(X;Y)$, over
convex regions. When restricted to the so-called transportation polytopes (sets
of distributions with fixed marginals), very simple proofs of NP-hardness are
obtained for these problems because in that case they are all equivalent, and
their connection to the well-known \textsc{Subset sum} and \textsc{Partition}
problems is revealed. The computational intractability of the more general
problems over arbitrary polytopes is then a simple consequence. Further, a
simple class of polytopes is shown over which the above problems are not
equivalent and their complexity differs sharply, namely, minimization of
$H(X,Y)$ and $H(Y|X)$ is trivial, while minimization of $H(X|Y)$ and
maximization of $I(X;Y)$ are strongly NP-hard problems. Finally, two new
(pseudo)metrics on the space of discrete probability distributions are
introduced, based on the so-called variation of information quantity, and
NP-hardness of their computation is shown.

本研究探讨了 Shannon 信息度量的某些优化问题，包括在凸区域上极小化联合和条件熵（H（X，Y），H（X | Y），H（Y | X））和最大化互信息（I（X；Y）），并介绍了新（伪）度量，并证明了它们的计算是 NP-hard 的。