On the Parameterized Complexity of Default Logic and Autoepistemic Logic

Arne Meier, Johannes Schmidt, Michael Thomas, Heribert Vollmer

Abstract

We investigate the application of Courcelle's Theorem and the logspace version of Elberfeld et al. in the context of the implication problem for propositional sets of formulae, the extension existence problem for default logic, as well as the expansion existence problem for autoepistemic logic and obtain fixed-parameter time and space efficient algorithms for these problems. On the other hand, we exhibit, for each of the above problems, families of instances of a very simple structure that, for a wide range of different parameterizations, do not have efficient fixed-parameter algorithms (even in the sense of the large class XPnu), unless P=NP.

Introduction

Non-monotonic reasoning was introduced in the 1970s to better model human cognitive processes, specifically the ability to make assumptions and revise them in the light of new information. Among the most prominent frameworks are Default Logic, which utilizes "rules of thumb" to handle incomplete information, and Autoepistemic Logic, which models the beliefs of a rational, self-reflective agent.

While these logics are powerful, they are computationally daunting. Standard propositional logic (SAT) is NP-complete, but the decision problems for Default and Autoepistemic logics—such as determining the existence of an extension or expansion—are typically $\Sigma^p_2$-complete. This puts them a full level higher on the polynomial hierarchy, making them effectively unusable for large-scale AI applications without identifying specific "islands of tractability." This paper explores whether parameterized complexity, specifically using the graph-theoretic measure of tree width, can provide such an island.

Methodology: Meta-Theorems and Graph Encodings

The research employs a "meta-theorem" approach to establish tractability. The authors first translate the complex logical requirements of Default and Autoepistemic logic into Monadic Second-Order (MSO) logic. This involves representing a knowledge base as a graph where nodes represent formulas or variables, and edges represent their logical relationships.

By leveraging Courcelle’s Theorem, which states that any property expressible in MSO logic can be decided in linear time on graphs with bounded tree width, the authors prove that these problems are Fixed-Parameter Tractable (FPT). Furthermore, they utilize recent advancements by Elberfeld et al. to demonstrate that these problems are not only time-efficient but also space-efficient, belonging to the class PLS (Parameterized Logspace).

To establish the limits of this tractability, the authors introduce a novel graph construction called a "pseudo-clique." This construction allows them to prove lower bounds, showing that even restricted versions of these logics can generate high tree width, thereby preventing a simple escape from the underlying complexity.

Key Insights

Tree Width as a Structural Key

The paper reinforces the significance of tree width as a fundamental complexity metric. If the connections between facts in a knowledge base are sufficiently "tree-like," even the most daunting $\Sigma^p_2$-complete logical problems become solvable. This provides a rigorous mathematical basis for why certain structured knowledge bases are easier to reason with than others.

The Space Dimension

While most parameterized complexity research focuses on time, this work highlights space complexity. By showing that bounded tree width allows for algorithms in Parameterized Logspace, the authors suggest that these complex reasoning tasks can be performed with extremely low memory overhead, provided the structure is simple enough.

The Deception of Syntactic Simplicity

A significant finding is that syntactic simplicity does not guarantee computational ease. One might assume that a logic restricted to simple literals (e.g., $x$ or $\neg y$) would be easier to process. However, the authors demonstrate that even these simple rules can be woven into complex "pseudo-cliques." This proves that tree width is a "non-trivial" parameter; there are simple-looking problems that still possess high structural complexity and remain intractable.

Results and Hardness

  • Tractability: The Extension Existence Problem (Default Logic) and the Expansion Existence Problem (Autoepistemic Logic) are confirmed to be FPT and in PLS when parameterized by the tree width of the knowledge base.
  • Hardness: For many other common parameters (such as those typically used for SAT), these problems remain outside the class $XP_{nu}$. This implies they are likely not solvable in polynomial time even for fixed parameter values, unless $P = NP$.
  • Structural Proof: Theorem 13 and 19 demonstrate that a pseudo-clique of size $n$ has a tree width of $n-1$, providing a formal tool to show that restricted logical fragments can still exhibit maximum structural complexity.

Conclusion

This research identifies tree width as a viable path toward making non-monotonic reasoning practical, while simultaneously cautioning that other forms of simplification are insufficient. While the theoretical results are promising, the authors acknowledge a practical limitation: the constant factors associated with Courcelle’s Theorem are often quite large. Future work will focus on identifying other non-trivial parameters that are less restrictive than tree width and further exploring space-parameterized complexity classes like PLS and FPL in broader AI contexts.

Summary updated

Abstract

We investigate the application of Courcelle's Theorem and the logspace version of Elberfeld etal. in the context of the implication problem for propositional sets of formulae, the extension existence problem for default logic, as well as the expansion existence problem for autoepistemic logic and obtain fixed-parameter time and space efficient algorithms for these problems. On the other hand, we exhibit, for each of the above problems, families of instances of a very simple structure that, for a wide range of different parameterizations, do not have efficient fixed-parameter algorithms (even in the sense of the large class XPnu), unless P=NP.
BibTeX
@inproceedings{meier2012parameterized,
  author = {Arne Meier and Johannes Schmidt and Michael Thomas and Heribert Vollmer},
  title = {{On the Parameterized Complexity of Default Logic and Autoepistemic Logic}},
  booktitle = {LATA},
  year = {2012},
  doi = {10.1007/978-3-642-28332-1\_33},
}
Figure