PostScript

*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.

nir@cs.huji.ac.il