Busca avançada
Ano de início
Entree


The Descriptive Complexity of Bayesian Network Specifications

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