Non-Elementary Speed-Ups in Default Reasoning

. Default logic is one of the most prominent formalizations of common-sense reasoning. It allows "jumping to conclusions" in case that not all relevant information is known. However, theoretical complexity results imply that default logic is (in the worst case) computationally harder than classical logic. This somehow contradicts our intuition about common-sense reasoning: default rules should help to speed up the reasoning process, and not to slow it down. In this paper, we show that default logic can indeed deliver the goods. We consider a sequent-calculus for first-order default logic and show that the presence of defaults can tremendously simplify the search of proofs. In particular, we show that certain sequents have only long "classical" proofs, but short proofs can be obtained by using defaults. 1 Introduction In recent years, the complexity of non-monotonic reasoning techniques has been thoroughly investigated (e.g. [9, 10, 11, 15], an overview is given in [6]). It turned out ..