Source-linked AI summary
On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions
Guy Emerson
TL;DR
The paper asks whether two conditionals represented compactly can be compatible with a joint distribution, a question that matters when explicit tables are infeasible. It formalises conditionals as succinct arithmetic circuits and proves intractability across several compatibility notions, including cases where no succinct joint exists. These results identify a trade-off among computational tractability, model flexibility, and probabilistic coherence.
Problem
The paper studies compatibility of conditional distributions in succinct representations, motivated by high-dimensional settings where enumerating all distribution values is prohibitive.
Method
The paper formalises conditional distributions as tractable arithmetic circuits and analyzes strong, weak, tractably valued, and succinct-joint compatibility.
Results
Strong and weak compatibility with zero probabilities are PSPACE-complete, while non-zero compatibility is co-NP-complete and some compatible conditionals lack succinctly representable joints unless the polynomial hierarchy collapses.
Takeaways & Limitations
The results demonstrate a trade-off between computational tractability, model flexibility, and probabilistic coherence in high-dimensional probabilistic models.
Takeaways & Limitations
The hardness results rely on arithmetic circuits flexible enough to simulate Boolean circuits; restricting the circuit class can make Bayesian inference tractable.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper formalises compatibility for conditionals represented succinctly by arithmetic circuits, targeting high-dimensional settings where explicit distribution tables are impractical. It proves that this succinct compatibility problem is computationally intractable, with complexity depending on whether zero probabilities are allowed and whether the joint must itself be succinct.
- Problem: The paper studies whether two succinct conditional distributions p(x|y) and p(y|x) are compatible with any joint distribution p(x,y).For table-encoded discrete conditionals, compatibility can be formulated as a tractable constraint-satisfaction problem.
- Motivation: High-dimensional distributions can be prohibitive to store by enumeration, motivating succinct arithmetic-circuit representations with succinctly expressible values.The paper notes that this setting includes probabilistic models such as Bayesian networks and can encompass neural-network-style computations.
- Results: With non-zero probabilities, succinct compatibility is co-NP-complete because incompatibility can be witnessed by local constraint violations.When zero probabilities are allowed, the induced graph can contain multiple strongly connected components, distinguishing strong from weak compatibility.
- Results: Strong and weak compatibility are both PSPACE-complete when probabilities may be zero.Strong compatibility requires all relevant components to be compatible, whereas weak compatibility requires at least one compatible component.
- Results: Compatibility with a tractably valued joint remains PSPACE-complete, while compatibility with a succinctly expressible joint has lower stated complexity under the polynomial-hierarchy assumption.The paper further reports compatible succinct conditionals whose joints cannot be represented by succinct circuits, assuming ΣP 2 ≠ PSPACE.
2 Succinct Circuit Representations of Distributions
The paper represents distributions over Boolean vectors using arithmetic circuits whose inputs encode variable assignments and whose outputs encode probabilities. Tractability requires bounded intermediate bit lengths, while succinct representability additionally requires polynomial circuit size.
- Circuit representation: An arithmetic circuit takes Boolean-variable assignments as input and produces a distribution probability as output.Nodes are inputs, integer constants, or binary addition and multiplication operations, with selected output nodes.
- Circuit representation: A conditional p(x|y) is represented by treating both x and y as circuit inputs, with rational probabilities encoded using two output nodes.The circuit must also permit tractable computation of every node.
- Tractability: A tractable circuit representation has exactly two output nodes and polynomially bounded binary representations for every node value.The stated definition uses a bound by the circuit size; polynomial bounds yield the same distribution families after padding.
- Expressive power: These circuits can simulate arbitrary Boolean circuits and, with suitable operations, neural networks using piecewise polynomial activations such as ReLU.Numerical algorithms can also be approximated by discretising real numbers to a chosen accuracy.
- Succinctness: A distribution family is succinctly representable when it has tractable circuits of polynomially bounded size in the number of input nodes.This definition applies the succinct-representation idea to distributions rather than graphs.
3 The Succinct Compatibility Problem
The non-zero succinct compatibility problem is posed under an assumption that avoids undefined conditionals and is shown to be co-NP-complete. The proof uses exponentially many four-point constraints, local incompatibility certificates, and a reduction from Boolean tautology.
- Problem setup: The non-zero case assumes p(x|y) and p(y|x) are positive everywhere, avoiding undefined conditionals caused by zero-probability conditioning events.Circuit outputs may be normalised implicitly without changing compatibility complexity because probability ratios are invariant to normalisation.
- Complexity result: Determining compatibility for positive succinct conditionals is co-NP-complete.The result applies to tractable circuit representations of both conditional distributions.
- Upper bound: Compatibility requires checking a constraint for every quadruple (x1, x2, y1, y2), so any violating quadruple certifies incompatibility.Each certificate can be checked in linear time relative to the maximum circuit size.
- Upper bound: If all certificates are rejected, a joint distribution can be constructed from the conditionals and normalised by a constant α.The construction is then shown to reproduce both conditionals through the rejected-certificate constraints.
- Lower bound: Co-NP-hardness follows by reducing Boolean tautology to compatibility using conditionals whose circuits are linear in the formula length.The constructed conditionals are compatible exactly when the formula is true under every assignment.
4 Succinct Compatibility with Zeroes
Allowing zero probabilities distinguishes strong from weak compatibility and raises the complexity of succinct compatibility checks. The paper also shows that compatible conditionals may lack tractably valued or succinctly representable joints.
- Zero probabilities make compatibility non-unique because conditioning on a zero-probability event is undefined.
- Strong compatibility constrains every relevant component, whereas weak compatibility requires only one suitable strongly connected component.The non-zero graph represents conditional supports and their directed connections.
- PSPACE-complete is the complexity of deciding strong or weak compatibility for tractable circuit representations.
- An exponentially long support chain can make a compatible joint’s final probability doubly exponentially small, requiring exponentially many denominator digits.
- PSPACE-complete is also the complexity of deciding strong or weak compatibility with tractable values.
- ΣP-complete is the stated complexity of deciding compatibility with a tractable joint, while compatible conditionals can still lack succinctly representable joints.
- Loop constraints and polynomial-space path checks provide the upper-bound strategy, while quantifier gadgets support PSPACE-hardness.For weak compatibility, the algorithm searches for a suitable strongly connected component; a generalized gadget construction does not provide a tractable joint.
5 Algebraic Structure of Compatibility Constraints
The paper characterizes compatibility constraints algebraically using polygonal complexes and homology, then constructs succinct instances with many long independent constraints. These structures explain why finding non-local loops drives PSPACE complexity.
- Complexity: Finding longer loops is PSPACE-complete, whereas the all-non-zero case is co-NP-complete because local constraints fully characterize compatibility.A generating set of constraints suffices, and minimum-length representatives can be sought using st-connectivity procedures.
- Constraint structure: Non-local constraints are loop ratios that cannot be expressed as products of local constraints.Local constraints correspond to square faces, while triangular faces encode dependencies among edge ratios.
- Homological characterization: The number of independent non-local constraints equals the rank of the first homology group of the non-zero polygonal complex.This follows by identifying probability-ratio multiplication with addition of homological 1-chains and local constraints with face boundaries.
- Hard instances: Examples realize rank n −2, rank 1 with generating loops of length 2n, and rank n log n with 15-value constructions achieving rank 31.Some constructions also encode logical AND and OR gates, while Möbius-strip examples yield five independent local constraints and non-local loops of length 6 to 10.
- Hard instances: For n values, another construction makes both rank and generator length asymptotically 2√n.In the succinct setting, n = 2^k for k-dimensional inputs.
6 Discussion
The discussion frames succinct compatibility as a trade-off among computational tractability, model flexibility, and probabilistic coherence. Different modeling priorities lead to different compromises, including incoherent conditionals or computationally costly inference.
- Trade-offs: Succinct compatibility results demonstrate a trade-off between computational tractability, model flexibility, and probabilistic coherence in high-dimensional probabilistic models.The discussion presents this trade-off as a consequence of the paper’s intractability results.
- Trade-offs: Models grounded in strong structural beliefs may prioritize flexibility and coherence despite the computational cost of inference.The paper gives physics-based models as an example of this setting.
- Trade-offs: Restricting arithmetic circuits, for example to Probabilistic Circuits, can preserve tractable Bayesian inference while changing the available model class.The paper’s hardness results rely on arithmetic circuits flexible enough to simulate Boolean circuits.
- Trade-offs: Flexible tractable models may sometimes exhibit incoherence between their conditionals.This is the paper’s stated implication when tractability and flexibility are prioritized together.
- Conditional modeling: Because many applications require conditionals rather than joints, tractable joints impose a restriction on conditional flexibility.The discussion therefore gives theoretical motivation for developing models directly in terms of conditionals.