Complexity of argument‐based default reasoning with specificity

Article type: Research Article

Authors: Zhao, Xishun

Affiliations: Institute of Logic and Cognition, Zhongshan University, Guangzhou 510275, P. R. China E‐mail: lcxszhao@hotmail.com

Abstract: In this paper we investigate the complexity of Dung and Son's approach to default reasoning with specificity. We show that the three decision problems: existence of extensions, brave reasoning and cautious reasoning are generally complete for the second level of the polynomial hierarchy. For some restricted cases, e.g., Horn and 2CNF default theories, all the three problems are intractable although classical brave reasoning in these cases is tractable. Finally, we show that stratification can not reduce the complexity of brave and cautious reasoning although it guarantees the existence of extensions.

Keywords: Default logic, complexity, default reasoning with specificity

Journal: AI Communications, vol. 16, no. 2, pp. 107-119, 2003