The complexity of reasoning for fragments of default logic (Q2893324)

This article analyzes the complexity of default logic by means of Post's lattice. The three usual decision problems (extension existence, credulous reasoning, and skeptical reasoning) are analyzed on default theories containing only formulas of the respective clones in Post's lattice, obtaining \(\Sigma_2\)-, \(\Pi^P_2\)-, \(\Delta^P_2\)-, NP-, coNP-, P-, and NL-completeness results for the three problems in the various fragments determined by Post's lattice. In some cases the complexity is also trivial: this happens for the extension existence problem, when for a fragment the existence of an extension is guaranteed. All the results are proved, and all hardness results are obtained via constant-depth reductions.NEWLINENEWLINEFigures 1 and 2 on pages 589 and 590 provide a good overview of the obtained results: Extension existence is \(\Sigma_2\)-complete for clones \(\supseteq S_1\) and \(D\); \(\Delta^P_2\)-complete for all other clones \(\supseteq S_{11}\); NP-complete for all other clones \(\supseteq N_2\) and \(L_0\); P-complete for all other clones \(\supseteq V_0\) or \(\supseteq E_0\); NL-complete for all other clones \(\supseteq I_0\); trivial for the remaining clones.NEWLINENEWLINECredulous reasoning is \(\Sigma^P_2\)-complete for clones \(\supseteq S_1\) and \(D\); \(\Delta^P_2\)-complete for all other clones \(\supseteq S_{11}\); coNP-complete for all other clones \(\supseteq D_2\), \(\supseteq S_{00}\), or \(\supseteq S_{10}\); NP-complete for all other clones \(\supseteq N_2\) and \(L_0\); P-complete for all other clones \(\supseteq V_2\), \(\supseteq L_2\), or \(\supseteq E_2\); NL-complete for the remaining clones.NEWLINENEWLINESkeptical reasoning is \(\Pi^P_2\)-complete for clones \(\supseteq S_1\) and \(D\); \(\Delta^P_2\)-complete for all other clones \(\supseteq S_{11}\); coNP-complete for all other clones \(\supseteq D_2\), \(\supseteq S_{00}\), \(\supseteq N_2\), or \(\supseteq S_{10}\), and \(L_0\); P-complete for all other clones \(\supseteq V_2\), \(\supseteq L_2\), or \(\supseteq E_2\); NL-complete for the remaining clones.NEWLINENEWLINEOne remark: at the end of the proof for Theorem 5.4 it appears as if a reference to another Lemma other than 5.2 was missing. As far as I can see, the sixth claim indeed follows from just Lemma 5.2.