Preferred arguments are harder to compute than stable extensions

Abstract

Based on an abstract framework for nonmonotonic reasoning, Bondarenko et at. have extended the logic programming semantics of admissible and preferred arguments to other nonmonotonic formalisms such as circumscription, autoepisternic logic and default logic. Although the new semantics have been tacitly assumed to mitigate the computational problems of nonmonotonic reasoning under the standard semantics of stable extensions, it seems questionable whether they improve the worst-case behaviour. As a matter of fact, we show that credulous reasoning under the new semantics in propositional logic programming and prepositional default logic has the same computational complexity as under the standard semantics. Furthermore, sceptical reasoning under the admissibility semantics is easier - since it is trivialised to monotonic reasoning. Finally, sceptical reasoning under the preferability semantics is harder than under the standard semantics.