First-Order Bayesian Network Specifications Capture the Complexity Class PP. (arXiv:1609.03437v1 [cs.AI])

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.

from cs.AI updates on arXiv.org http://ift.tt/2crzdKS
via IFTTT