Abduction and the Dualization Problem^{*}
(invited lecture for DS 2003)
Author: Thomas Eiter
Affiliation: KnowledgeBased Systems Group,
Institute of Information Systems,
Vienna University of Technology, Vienna, Austria
Abstract.
Abduction is a fundamental mode of reasoning which was extensively
studied by C.S. Peirce, who also introduced the term for inference of
explanations for observed phenomena. Abduction has taken on increasing
importance in Artificial Intelligence (AI) and related disciplines,
where it has been recognized as an important principle of commonsense
reasoning. It has applications in many areas of AI and Computer
Science including diagnosis, database updates, planning, natural
language understanding, learning, to number some of them.
In a logicbased setting, abduction can be viewed as the task to find,
given a set of formulas T (the background theory) and a formula Q (the
query), a minimal set of formulas E (an explanation) from a set of
abducibles A such that T union E is satisfiable and logically entails
Q. In many application scenarios T is a propositional Horn theory, Q
is a literal or a conjunction of literals, and the abducibles A are
certain literals of interest. For computing abductive explanations,
wellknown early systems such as Poole's Theorist or assumptionbased
Truth Maintenance Systems have been devised in the 1980s.
Besides computing some explanation, the problem of generating several
or all explanations has received more attention in the last
years. This is important since often one would like to select one out
of a set of alternative explanations according to a preference or
plausibility relation. In general, a query may have exponentially many
explanations, and thus efficient generation of all explanations may be
understood in terms of polynomial totaltime (or outputpolynomial
time), i.e., in time polynomial in the combined size of the input and
the output. Furthermore, if exponential resources are prohibitive, one
would like to know whether a few explanations (e.g., polynomially
many) can be generated in polynomial time.
In recent and ongoing work, we have investigated the computational
complexity of these issues, and compiled several results for charting
the tractability / intractability frontier of these problems. In this
talk, we shall recall some of the results and then focus on abduction
from Horn theories represented by their characteristic models. In this
setting, the background theory T is represented by a set of so called
characteristic models, charset(T), rather than by formulas. The
benefit is that for certain formulas, logical consequence from T
efficiently reduces to deciding consequence from charset(T) (which is
easy) and thus admits tractable inference. In fact, finding some
abductive explanation for a query literal is polynomial in this
setting, while this is wellknown to be NPhard under formulabased
representation.
Computing all abductive explanations for a query literal is
polynomialtime equivalent (in a precise sense) to the problem of
dualizing a Boolean function given by a monotone CNF. The latter
problem, Monotone Dualization, is with respect to complexity a
somewhat mysterious problem which since more than 20 years resists to
a precise classification in terms of wellestablished complexity
classes. Currently, no polynomial totaltime algorithm solving this
problem is known; on the other hand, there is also no stringent
evidence that such an algorithm is unlikely to exist (such as, eg.,
coNPhardness of the associated decision problem whether, given two
monotone CNFs F and G, they represent dual functions). On the
contrary, results in the 1990's provided some hints that the problem
is closer to polynomial totaltime, since as shown by Fredman and
Khachyian, the decisional variant can be solved in quasipolynomial
time, i.e., in time O(n^{log n}). This was recently refined to
solvability in polynomial time with limited nondeterminism, i.e.,
using a polylogarithmic number of bit guesses. We will consider some
possible extensions of the results for abductive explanations which
are polynomialtime equivalent to Monotone Dualization.
Apart from this peculiarity, Monotone Dualization has been recognized
as an important problem since there are a large number of other
problems in Computer Science which are known to be polynomialtime
equivalent to this problem. It has a role similar to the one of SAT
for the class NP: A polynomial totaltime algorithm for Monotone
Dualization implies polynomial totaltime algorithms for all the
polynomialtime equivalent problems.
We consider some possible extensions og the results for abductive
explanations which are polynomialtime equivalent to Monotone Dualization.
Besides generating all abductive explanations for a literal,
there are many other problems in
Knowledge Discovery and Data Mining which are polynomialtime
equivalent or closely related to Monotone Dualization, including
learning with oracles, computation of infrequent and frequent sets,
and key generation. We shall give a brief account of such problems,
and finally will conclude with some open problems and issues for
future research.
The results presented are joint work with Kazuhisa Makino, Osaka
University.
^{*}The full version of this paper is
published in the Proceedings of the 6th International Conference
on Discovery Science, Lecture Notes in Artificial Intelligence Vol. 2843
©Copyright 2003 SPRINGER
