On the Parameterized Complexity of Default Logic and Autoepistemic Logic

Arne Meier, Johannes Schmidt, Michael Thomas, Heribert Vollmer

TL;DR

This paper demonstrates that while reasoning in non-monotonic logics is generally "super-hard" ($\Sigma^p_2$-complete), it becomes efficiently solvable (Fixed-Parameter Tractable) if the underlying knowledge base has a simple graph structure (low tree width). However, the authors also prove that even the simplest possible versions of these logics remain intractable for most other ways of measuring "simplicity," unless major complexity classes like P and NP collapse.

What Problem Does This Paper Address?

In the 1970s, researchers introduced non-monotonic reasoning to model how humans think—specifically, how we make assumptions and revise them when new information arrives. Two heavyweights in this field are Default Logic (using "rules of thumb") and Autoepistemic Logic (modeling the beliefs of a rational agent).

The catch? These logics are computationally brutal. While standard propositional logic (SAT) is NP-complete, these non-monotonic variants are typically $\Sigma^p_2$-complete, sitting a full level higher on the polynomial hierarchy. To make these logics usable in AI, researchers look for "islands of tractability"—specific subsets of problems that are actually solvable in a reasonable amount of time. This paper investigates whether parameterized complexity (specifically using the graph-theoretic measure of tree width) can provide such an island.

Methods

The authors employ a powerful "meta-theorem" approach:

  1. MSO Encodings: They 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 are formulas or variables and edges represent their relationships.
  2. Courcelle’s Theorem: This famous theorem states that any property expressible in MSO logic can be decided in linear time on graphs with bounded tree width.
  3. Logspace Extensions: They go a step further by using recent improvements (by Elberfeld et al.) to show that these problems aren't just fast (FPT), but also space-efficient (belonging to the class PLS—Parameterized Logspace).
  4. Pseudo-Cliques: To prove lower bounds, the authors introduce a novel graph construction called a "pseudo-clique." This allows them to show that even very restricted versions of the logic can generate graphs with high tree width, preventing a "cheap" escape from complexity.

Datasets

As a theoretical computer science paper, no empirical datasets were used. The "data" consists of mathematical structures: propositional formulas, default theories, and graph-theoretic encodings of knowledge bases.

Key Insights and Ideas

  • Tree Width as a Universal Key: The paper reinforces the idea that tree width is a fundamental "complexity dial." If the connections between your facts are "tree-like" enough, even the most daunting logical problems become tractable.
  • The Space Dimension: Most parameterized complexity research focuses on time. This paper highlights space complexity, showing that bounded tree width allows for algorithms that are extremely memory-efficient.
  • Syntactic Simplicity is Deceptive: You might think that a logic using only simple "literals" (like $x$ or $\neg y$) would be easy. The authors show this is false. Even these "simple" rules can be woven into complex "pseudo-cliques" that make reasoning just as hard as the general case.
  • Non-Triviality of Tree Width: By constructing pseudo-cliques, the authors prove that tree width is a "non-trivial" parameter for these logics—meaning there are simple-looking problems that still have high tree width.

Key Results

  • Tractability: The Extension Existence Problem (Default Logic) and the Expansion Existence Problem (Autoepistemic Logic) are Fixed-Parameter Tractable (FPT) and in Parameterized Logspace (PLS) when parameterized by the tree width of the knowledge base.
  • Hardness: For many other common parameters (like those used for SAT), these problems remain outside the class $XP_{nu}$ (meaning they are likely not solvable in polynomial time even for fixed parameter values) unless $P = NP$.
  • Structural Proof: Theorem 13/19 proves that a pseudo-clique of size $n$ has a tree width of $n-1$, providing a tool to prove that certain restricted logical fragments still possess high structural complexity.

Limitations and Future Work

The primary limitation is that while tree width provides a theoretical "island of tractability," the constant factors hidden in the "O" notation of Courcelle’s Theorem are often astronomically large, making direct implementation difficult.

The authors suggest two main paths for future research:

  1. Finding other "non-trivial" parameters that allow for efficient reasoning but aren't as restrictive as tree width.
  2. Further exploring the newly defined space-parameterized complexity classes (like PLS and FPL) to see how they apply to other areas of Artificial Intelligence.

Summary updated

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.
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},
}

Loading related content...

Figure