Hard problems for simple default logics

摘要

We investigate the complexity of reasoning with a number of limited default logics. Surprising negative results (the high complexity of simple three literal default rules) as well as positive results (a fast algorithm for skeptical reasoning with binary defaults) are reported, and sources of complexity are discussed. These results impact on work on defeasible inheritance hierarchies as well as default reasoning in general.