On the Complexity of Conditional Logics
N. Friedman and J. Y. Halpern
In J. Doyle, E.
Sandwell, and P. Torasso, eds. Principles of Knowledge
Representation and Reasoning: Proc. Fourth International Conference
(KR'94). Morgan Kaufman, San Francisco, CA. 1994. 202-213.
Postscript
version (248K)
PDF
version.
Abstract
Conditional logics, introduced by Stalnaker and Lewis, have
been utilized in artificial intelligence to capture a broad range
of phenomena. In this paper we examine the complexity of several variants
discussed in the literature. We show that, in general, deciding
satisfiability is
PSPACE-complete for formulas with arbitrary conditional nesting
and NP-complete for formulas with bounded nesting of conditionals.
However, we provide several exceptions to this rule. Of particular
note are results showing that (a) when assuming uniformity
(i.e., that all worlds agree on what worlds are possible), the
decision problem becomes EXPTIME-complete even for formulas with
bounded nesting, and (b) when assuming absoluteness (i.e.,
that all worlds agree on all conditional statements), the decision
problem is NP-complete for formulas with arbitrary nesting.
Back to Nir's
publications page
nir@cs.huji.ac.il