First-Order Bayesian Network Specifications Capture the Complexity Class PP
arXiv:1609.03437v1
AI Analysis
This result is foundational for theoretical computer science and AI, linking probabilistic reasoning and complexity theory, but it is incremental as it builds on known connections between PP and Bayesian networks.
The paper proves that a language belongs to the complexity class PP if and only if its strings encode valid inferences in Bayesian networks defined using function-free first-order logic with equality, establishing a precise equivalence between these computational and logical frameworks.
The point of this note is to prove that a language is in the complexity class PP if and only if the strings of the language encode valid inferences in a Bayesian network defined using function-free first-order logic with equality.