Complexity of normal default logic and related modes of nonmonotonic reasoning

Normal default logic, the fragment of default logic obtained by restricting defaults to rules to the form α:Mβ/β. is the most important and widely studied part of default logic. In Annals of Pure and Applied Logic, vol. 67, pp. 269-324 (1994), we proved a basis theorem for extensions of recursive propositional logic normal default theories and hence for finite predicate logic normal default theories, i.e. we proved that every recursive propositional normal default theory possesses an extension which is recursively enumerable (r.e.) in 0´. In this paper, we show that this bound is tight. Specifically, we show that for every r.e. set A and every B which is r.e. in A, there is a recursive normal default theory ⟨D,W⟩ with a unique extension which is Turing-equivalent to A⊕B. A similar result holds for finite predicate logic normal default theories