| Texto completo | |
| Autor(es): |
Cozman, Fabio G.
;
Maua, Denis D.
;
Antonucci, A
;
Cholvy, L
;
Papini, O
Número total de Autores: 5
|
| Tipo de documento: | Artigo Científico |
| Fonte: | SYMBOLIC AND QUANTITATIVE APPROACHES TO REASONING WITH UNCERTAINTY, ECSQARU 2017; v. 10369, p. 11-pg., 2017-01-01. |
| Resumo | |
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. (AU) | |
| Processo FAPESP: | 15/21880-4 - PROVERBS -- Sistemas Booleanos Probabilísticos Super-restritos: ferramentas de raciocínio e aplicações |
| Beneficiário: | Marcelo Finger |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |