Some Computational Aspects of Circumscription

Phokion G. Kolaitis, Christos H. Papadimitriou

Introduction

In the field of artificial intelligence, formalizing "common-sense" reasoning requires systems that can handle non-monotonicity—the ability to retract conclusions when new information is presented. One of the most influential frameworks for this is circumscription, introduced by John McCarthy. Circumscription formalizes the notion of minimality: it asserts that a predicate $P$ holds for a specific set of entities and nothing else.

While conceptually powerful, circumscription poses significant computational challenges. Mathematically, circumscribing a First-Order (FO) formula typically results in a Second-Order (SO) formula. Because second-order logic lacks a complete deductive system and is often computationally intractable, a critical question arises: Under what conditions does the circumscription of a first-order formula "collapse" back into a first-order formula? This paper investigates the boundaries of this expressibility and the resulting complexity of model checking.

The Existential "Safe Zone"

A primary contribution of this research is the identification of a class of formulas for which circumscription is always well-behaved. The authors demonstrate that for any existential first-order formula (sentences beginning with an existential quantifier $\exists$), the circumscribed version is guaranteed to remain within first-order logic.

To prove this, the authors utilize logical reductions involving "complete disjunctive normal forms" and "equality types." This result provides a theoretical guarantee for researchers using existential expressions, ensuring that their reasoning remains within the relatively efficient bounds of first-order logic. However, the authors note a potential practical limitation: even when a first-order equivalent exists, the resulting formula may be exponentially larger than the original, a phenomenon that warrants further investigation into the inherent size complexity of these transformations.

The Universal "Wall" and Undecidability

The computational landscape shifts dramatically when considering universal formulas (sentences beginning with a universal quantifier $\forall$). The authors focus on logic programs, specifically conjunctions of function-free Horn clauses, and bridge the gap between logic and database theory.

They establish a definitive link: the circumscription of a logic program is first-order expressible if and only if the logic program is "bounded." A logic program is considered bounded if it reaches its fixed-point result in a constant number of steps, regardless of the size of the input structure.

This connection leads to a sobering conclusion. Because the problem of determining "boundedness" has been proven undecidable, the authors show that it is also undecidable to determine whether a given universal first-order formula has a first-order circumscription. There is no general algorithm that can tell a researcher whether their universal model will collapse into first-order logic or remain in the more complex second-order realm.

Complexity of Model Checking

Beyond the question of expressibility, the paper examines the actual cost of verifying whether a finite structure satisfies a circumscribed formula (model checking). In standard first-order logic, model checking is highly efficient and can be performed in polynomial time relative to the size of the structure.

The authors prove that circumscription can break this efficiency. By reducing a 3SAT problem to a graph-theoretic problem (specifically, finding simple subgraphs in cubic graphs), they demonstrate that there exists a specific first-order sentence whose circumscription results in a coNP-complete model-checking problem. This represents a significant jump in computational complexity, moving from the tractable polynomial-time domain into a class of problems generally considered hard to solve.

Conclusion and Future Directions

This research delineates the computational boundaries of circumscription, highlighting a sharp contrast between existential and universal quantification. While existential formulas offer a guarantee of first-order expressibility, universal formulas lead to undecidability and increased computational complexity.

Future work remains in several areas:

  1. Size Complexity: Investigating whether the exponential blow-up in existential circumscription is avoidable.
  2. Finite Structures: Determining if the undecidability of boundedness holds specifically for finite structures, which are the primary concern of database theory.
  3. Subclass Identification: Searching for restricted subclasses of universal formulas where first-order expressibility might still be algorithmically detectable.

By mapping these boundaries, the authors provide a clearer understanding of the trade-offs between the expressive power of non-monotonic reasoning and the computational costs of implementing it.

Summary updated

Abstract

The effects of circumscribing first-order formulas are explored from a computational standpoint. First, extending work of V. Lifschitz, it is Shown that the circumscription of any existential first-order formula is equivalent to a first-order formula. After this, it is established that a set of universal Horn clauses has a first-order circumscription if and only if it is bounded (when considered as a logic program); thus it is undecidable to tell whether such formulas have first-order circumscription. Finally, it is shown that there arefirst-order formulas whode circumscription has a coNP-complete model-checking problem.
BibTeX
@inproceedings{kolaitis1988some,
  author = {Phokion G. Kolaitis and Christos H. Papadimitriou},
  title = {{Some Computational Aspects of Circumscription}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure