{"id":"arxiv/2608.31120","url":"https://arxiv.org/abs/2608.31120","tags":["cs.LG","cs.CC","math.PR"],"score":0,"title":"On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions","domain":"cs.LG","source":"arxiv","authors":["Guy Emerson"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-31","reactions":{}}