The Complexity of Closed World Reasoning and Circumscription
Abstract
Closed world reasoning is a common nonmono-tonic technique that allows for dealing with neg-ative information in knowledge and data bases. We present a detailed analysis of the compu-tational complexity of the different forms of closed world reasoning for various fragments of propositional logic. The analysis allows us to draw a complete picture of the tractabil-ity/intractability frontier for such a form of non-monotonic reasoning. We also discuss how to use our results in order to characterize the com-putational complexity of other problems related to nonmonotonic inheritance, diagnosis, and de-fault reasoning. 1
Cite
Text
Cadoli and Lenzerini. "The Complexity of Closed World Reasoning and Circumscription." AAAI Conference on Artificial Intelligence, 1990.Markdown
[Cadoli and Lenzerini. "The Complexity of Closed World Reasoning and Circumscription." AAAI Conference on Artificial Intelligence, 1990.](https://mlanthology.org/aaai/1990/cadoli1990aaai-complexity/)BibTeX
@inproceedings{cadoli1990aaai-complexity,
title = {{The Complexity of Closed World Reasoning and Circumscription}},
author = {Cadoli, Marco and Lenzerini, Maurizio},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {1990},
pages = {550-555},
url = {https://mlanthology.org/aaai/1990/cadoli1990aaai-complexity/}
}