TY - GEN
T1 - The descriptive complexity of Bayesian network specifications
AU - Cozman, Fabio G.
AU - Mauá, Denis D.
PY - 2017/1/1
Y1 - 2017/1/1
N2 - © Springer International Publishing AG 2017. We adapt the theory of descriptive complexity to Bayesian networks, by investigating how expressive can be specifications based on predicates and quantifiers. We show that Bayesian network specifications that employ first-order quantification capture the complexity class PP; that is, any phenomenon that can be simulated with a polynomial time probabilistic Turing machine can be also modeled by such a network. We also show that, by allowing quantification over predicates, the resulting Bayesian network specifications capture the complexity class PPNP, a result that does not seem to have equivalent in the literature.
AB - © Springer International Publishing AG 2017. We adapt the theory of descriptive complexity to Bayesian networks, by investigating how expressive can be specifications based on predicates and quantifiers. We show that Bayesian network specifications that employ first-order quantification capture the complexity class PP; that is, any phenomenon that can be simulated with a polynomial time probabilistic Turing machine can be also modeled by such a network. We also show that, by allowing quantification over predicates, the resulting Bayesian network specifications capture the complexity class PPNP, a result that does not seem to have equivalent in the literature.
UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85025146815&origin=inward
UR - https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=85025146815&origin=inward
U2 - 10.1007/978-3-319-61581-3_9
DO - 10.1007/978-3-319-61581-3_9
M3 - Conference contribution
SN - 9783319615806
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 93
EP - 103
BT - The descriptive complexity of Bayesian network specifications
T2 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Y2 - 1 January 2018
ER -