Wyner's Common Information and the Common Entropy are NP-Hard to Compute
Abstract
Wyner's common information J(p) and the common entropy G(p) of a pair of random variables (X,Y) with finite ranges and joint distribution p are both defined by an optimization over the auxiliary random variables W that make X and Y conditionally independent: J(p) is the infimum of the mutual information I(X,Y;W), and G(p) is the infimum of the entropy H(W). We prove that both quantities are NP-hard to compute. For Wyner's common information, deciding whether J(p) is strictly smaller than a given integer r is NP-hard, and the problem is NP-complete on tables that are uniform on their support and have the same number of positive entries in every row. The reduction is from Maximum Edge Biclique and rests on an exact criterion, in terms of rectangles in the support of p, for improving on the auxiliary W=X; every yes-instance satisfies J(p)<r−1/(4N2) and every no-instance satisfies J(p)=r, where N is the number of positive entries of p. For the common entropy, deciding whether G(p)≤ r for a rational number r is NP-hard, even for tables with at most four nonzero entries in each row, all taking one of two values. The reduction is from exact cover by $3$-sets and rests on a majorization property of the masses of the nonnegative rank-one decompositions of p, combined with a quantitative form of the Schur concavity of entropy. In both cases the separation between yes- and no-instances is inverse-polynomial in the size of p, so that approximating J(p) or G(p) within a suitable inverse-polynomial additive error is also NP-hard. The two mechanisms are genuinely different: we exhibit a table on which a large rectangle in the support lowers J below the threshold of our first reduction while leaving G on it.
Related
- The entropy production is not always monotone for hard spheres or for Maxwell molecules
- The Algebraicity Problem for Hard-Core Entropy Constants on the Discrete Hypertori
- Four-Level Quantized Soft Information Aided Hard-Decision Decoder for Product-like Codes
- Exact Common Information and Exact Channel Synthesis for Correlated Discrete Sources
- The Information Bottleneck is NP-hard
BibTeX
@misc{bruno2026wyners,
title = {{Wyner's Common Information and the Common Entropy are NP-Hard to Compute}},
author = {Roberto Bruno and Ugo Vaccaro},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15402},
eprint = {2610.15402},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15402},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Wyner's Common Information and the Common Entropy are NP-Hard to Compute
AU - Roberto Bruno
AU - Ugo Vaccaro
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15402
UR - https://arxiv.org/abs/2610.15402
AB - Wyner's common information J(p) and the common entropy G(p) of a pair of random variables (X,Y) with finite ranges and joint distribution p are both defined by an optimization over the auxiliary random variables W that make X and Y conditionally independent: J(p) is the infimum of the mutual information I(X,Y;W), and G(p) is the infimum of the entropy H(W). We prove that both quantities are NP-hard to compute. For Wyner's common information, deciding whether J(p) is strictly smaller than a given integer r is NP-hard, and the problem is NP-complete on tables that are uniform on their support and have the same number of positive entries in every row. The reduction is from Maximum Edge Biclique and rests on an exact criterion, in terms of rectangles in the support of p, for improving on the auxiliary W=X; every yes-instance satisfies J(p)<r−1/(4N^2) and every no-instance satisfies J(p)=r, where N is the number of positive entries of p. For the common entropy, deciding whether G(p)≤ r for a rational number r is NP-hard, even for tables with at most four nonzero entries in each row, all taking one of two values. The reduction is from exact cover by $3$-sets and rests on a majorization property of the masses of the nonnegative rank-one decompositions of p, combined with a quantitative form of the Schur concavity of entropy. In both cases the separation between yes- and no-instances is inverse-polynomial in the size of p, so that approximating J(p) or G(p) within a suitable inverse-polynomial additive error is also NP-hard. The two mechanisms are genuinely different: we exhibit a table on which a large rectangle in the support lowers J below the threshold of our first reduction while leaving G on it.
ER -