On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions
Abstract
The motivation for this paper is the investigation of the trade-offs implicit in probabilistic models used in machine learning. Models are often used to make predictions in the form of conditional probabilities. However, a pair of conditional distributions p(x|y) and p(y|x) may not be compatible with any joint distribution p(x,y). Given two such conditionals, determining if there exists a compatible joint is known as the compatibility problem. For discrete random variables, when the conditionals are encoded as probability tables, the compatibility problem has a known solution, which is computationally tractable. In this paper, we formalise and study a succinct version of the problem, encoding conditional distributions as arithmetic circuits. This is applicable to practical applications of probabilistic modelling in high-dimensional settings, including neural network models. We show that, for succinct circuit representations of conditionals, the compatibility problem is intractable. In the case that all probabilities are non-zero, the problem is co-NP-complete. In the case that probabilities can be zero, we give examples to demonstrate that several notions of compatibility can be distinguished, and we prove that multiple versions of the problem are PSPACE-complete. Furthermore, we show that, assuming the polynomial hierarchy does not collapse, there exist compatible succinct conditionals whose joint cannot be expressed succinctly. Implications of these results for probabilistic modelling and machine learning are discussed.
Related
- Combinatorial Characterizations of the Learnability of Conditional Distributions
- Measuring Differences between Conditional Distributions using Kernel Embeddings
- On the continuity of conditional distributions and stratification for derivative pricing
- Non-Terminal Complexity of Simple Semi-Conditional Grammars
- Parallel gradient boosting for flexible estimation of conditional distributions
BibTeX
@misc{emerson2026complexity,
title = {{On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions}},
author = {Guy Emerson},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.31120},
eprint = {2608.31120},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.31120},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions
AU - Guy Emerson
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2608.31120
UR - https://arxiv.org/abs/2608.31120
AB - The motivation for this paper is the investigation of the trade-offs implicit in probabilistic models used in machine learning. Models are often used to make predictions in the form of conditional probabilities. However, a pair of conditional distributions p(x|y) and p(y|x) may not be compatible with any joint distribution p(x,y). Given two such conditionals, determining if there exists a compatible joint is known as the compatibility problem. For discrete random variables, when the conditionals are encoded as probability tables, the compatibility problem has a known solution, which is computationally tractable. In this paper, we formalise and study a succinct version of the problem, encoding conditional distributions as arithmetic circuits. This is applicable to practical applications of probabilistic modelling in high-dimensional settings, including neural network models. We show that, for succinct circuit representations of conditionals, the compatibility problem is intractable. In the case that all probabilities are non-zero, the problem is co-NP-complete. In the case that probabilities can be zero, we give examples to demonstrate that several notions of compatibility can be distinguished, and we prove that multiple versions of the problem are PSPACE-complete. Furthermore, we show that, assuming the polynomial hierarchy does not collapse, there exist compatible succinct conditionals whose joint cannot be expressed succinctly. Implications of these results for probabilistic modelling and machine learning are discussed.
ER -