On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions
cs.LG · cs.CC · math.PR
Quick verdict
Proves succinct conditional-distribution compatibility is co-NP-, PSPACE- and Σ2P-complete; rigorous and significant, with a few proof steps only sketched.
Summary
This theory paper formalises the compatibility problem—deciding whether two conditional distributions p(x|y) and p(y|x) arise from some joint distribution—for conditionals encoded as succinct arithmetic circuits, the setting relevant to high-dimensional and neural-network-style probabilistic models. When all probabilities are positive, compatibility is co-NP-complete (Theorem 1), proved via the four-point constraints of Arnold and Gokhale plus a reduction from tautology. When zeros are allowed, the paper distinguishes strong and weak compatibility, and proves both variants—and their 'tractable values' versions—PSPACE-complete (Theorems 2–3), using a nondeterministic graph-walk verifier and reductions from succinct graph connectivity and st-connectivity. Requiring the joint itself to be a succinct circuit lowers the problem to Σ2P-complete (Theorem 4), yielding the corollary that, unless the polynomial hierarchy collapses, some compatible succinct conditionals have succinctly valued joints with no succinct circuit representation. Section 5 characterises the number of independent non-local constraints as the rank of the first homology group of an associated polygonal complex, with constructions of high-rank, long-generator instances. Limitations: purely worst-case asymptotic theory; the loop-length bound underpinning the PSPACE verifier is justified only parenthetically; Section 5's rank computations are asserted without full proofs; no implementations or experiments.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 4 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Determining compatibility of succinctly (arithmetic-circuit) encoded conditionals is co-NP-complete when all probabilities are positive (Theorem 1).
- Strong and weak compatibility with zero probabilities — including the 'tractable values' variants — are PSPACE-complete (Theorems 2-3).
- Determining compatibility with a joint that is itself a succinct tractable circuit is Sigma-2-P-complete (Theorem 4).
- Unless the polynomial hierarchy collapses, some compatible succinct conditionals have succinctly valued joints that admit no succinct circuit representation (Corollary).
- The number of independent non-local compatibility constraints equals the rank of the first homology group of the non-zero polygonal complex (Theorem 5).
Strengths
First complexity treatment of a classical problem in the succinct setting
Formalises compatibility for circuit-encoded conditionals (Definitions 1-2) with a node bit-length bound motivated by the 2^(2^n) chain circuit in Section 2; the prior literature cited (Arnold-Press 1989 through Miranda-Zaffalon 2020) handles only explicit tables.
Complete complexity map with matching upper and lower bounds
co-NP (Theorem 1), PSPACE for strong/weak with and without tractable values (Theorems 2-3), Sigma-2-P for a tractable joint (Theorem 4); each has an explicit verifier and reduction. The Section 4.2 two-copy stationary-distribution gadget forcing contradictory pi(t):pi(s) ratios (1 vs 2) delivers hardness even under the tractable-values restriction, which Theorem 3's hardness needs.
Conceptually significant separation corollary
Structural theory beyond classification
Careful handling of definitional pitfalls
Weaknesses
Key correctness step of the PSPACE verifier is unproven
Section 5 results are asserted, not proved
Promise-problem status understated
Practice relevance argued by analogy only
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This is a single-author theory paper (arXiv, cs.LG + cs.CC + math.PR) with no experiments. It takes the classical compatibility problem for conditional distributions (Arnold and Press 1989) — given p(x|y) and p(y|x), does a joint p(x,y) exist with exactly these conditionals? — and studies it for the first time in the succinct setting: conditionals over {0,1}^n encoded as arithmetic circuits (Darwiche 2003) whose node values have bit-length bounded by circuit size (Definitions 1-2; the Section 2 chain circuit computing 2^(2^n) motivates the bound). Four decision problems are classified: positive conditionals (Theorem 1: co-NP-complete), strong and weak compatibility with zeros (Theorem 2: PSPACE-complete), with a 'tractable values' side condition (Theorem 3: PSPACE-complete), and with a succinct-circuit joint (Theorem 4: Sigma-2-P-complete). The Corollary derives a conditional separation between succinctly valued and succinctly representable joints. Theorem 5 with Definitions 10-12 gives a homological characterisation of the constraint structure. With two exceptions documented below, every claim is delivered with a complete proof.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 4 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is the compatibility problem for conditional distributions?
Given two conditional distributions p(x|y) and p(y|x), the compatibility problem asks whether some joint distribution p(x,y) has exactly these conditionals. For full probability tables over discrete variables it can be checked in polynomial time via four-point product conditions (Arnold and Press 1989; Arnold and Gokhale 1994). This paper shows the problem becomes intractable when the conditionals are given as compact arithmetic circuits.
What does 'succinct' representation mean in this paper?
Conditionals over boolean vectors {0,1}^n are arithmetic circuits (directed acyclic graphs of additions and multiplications over inputs and integer constants) in which every node's value has at most as many bits as the circuit size (Definition 1). A polynomial-size circuit therefore stands in for an exponentially large probability table, as in neural-network-style models.
How hard is it to check whether two learned conditional models are probabilistically consistent?
In the worst case for succinctly encoded conditionals: co-NP-complete when all probabilities are positive, and PSPACE-complete when zeros are allowed (even asking only for a joint with polynomially short probability values). So no efficient general algorithm should be expected unless standard complexity assumptions fail.
Does a compatible joint distribution always have a compact representation?
No. The paper's corollary shows that unless the polynomial hierarchy collapses, there are compatible succinctly encoded conditionals whose joint probabilities are all short to write down, yet no polynomial-size circuit represents the joint. Section 4 gives an explicit chain example (equation 9) where a joint probability needs an exponential number of digits.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The large zero-pattern matrices (12)-(15) are extracted as dot-matrices; their exact patterns were taken from the surrounding prose and not independently re-verified entry by entry.
- PDF extraction flattens superscripts (e.g. '2 1 2 k+1' for 2^((k+1)/2)); numeric exponents were reconstructed from context and cross-checked against footnote 3 and Section 5.1 prose.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.