Title: On the complexity of inference about probabilistic relational models
Abstract: We investigate the complexity of probabilistic inference from knowledge bases that encode probability distributions on finite domain relational structures. Our interest here lies in the complexity in terms of the domain under consideration in a specific application instance. We obtain the result that assuming NETIME≠ETIME this problem is not polynomial for reasonably expressive representation systems. The main consequence of this result is that it is unlikely to find inference techniques with a better worst-case behavior than the commonly employed strategy of constructing standard Bayesian networks over ground atoms (knowledge based model construction).
Publication Year: 2000
Publication Date: 2000-03-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 39
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot