First-Order Bayesian Network Specifications Capture the Complexity Class PP

Fabio Gagliardi Cozman

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 us…