Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!columbia!rutgers!ames!sdcsvax!ucbvax!osu-eddie.UUCP!tanner
From: tanner@osu-eddie.UUCP (Mike Tanner)
Newsgroups: comp.ai.digest
Subject: Re: Philosophy, Artificial Intelligence and Complexity Theory
Message-ID: <8705291548.AA02262@cbosgd.MIS.OH.ATT.COM>
Date: Fri, 29-May-87 11:48:17 EDT
Article-I.D.: cbosgd.8705291548.AA02262
Posted: Fri May 29 11:48:17 1987
Date-Received: Sun, 31-May-87 15:42:42 EDT
References: <8705251537.AA06291@seismo.CSS.GOV>
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: osu-eddie!tanner (Mike Tanner)
Distribution: world
Organization: The Ohio State University, CIS Dept.
Lines: 44
Approved: ailist@stripe.sri.com


We have a paper to appear in this year's IJCAI called "On the
computational complexity of hypothesis assembly", by Allemang, Tanner,
Bylander, and Josephson.

Hypothesis assembly is a part of many problem solving tasks.  Eg, in
medical diagnosis the problem is to find a collection of diseases
which are consistent, plausible, and collectively explain the
symptoms.

Our paper analyzes a particular algorithm we've developed for solving
this problem.  The algorithm turns out to be polynomial under certain
assumptions.  But the problem of hypothesis assembly is shown to be
NP-Complete, by reduction to 3-SAT, when those assumptions are
violated.  In particular, if there are hypotheses which are
incompatible with each other it becomes NP-complete.  (Another well
known algorithm for the same problem, Reggia's generalized set
covering model, is shown to be NP-complete also, by reduction to
vertex cover.)

The interesting part of the paper is the discussion of what this
means.  The bottom line is, people solve problems like this all the
time without apparent exponential increase in effort.  We take this to
mean human problem solvers are taking advantage of features of the
domain to properly organize their knowledge and problem solving
strategy so that these complexity issues don't arise.

In the particular case discussed in the paper the problem is the
identification of antibodies in blood prior to giving transfusions.
There exist pairs of antibodies that people simply cannot have both
of, for genetic reasons.  So we're in the NP-complete case.  But, it
is possible to reason up front about the antibodies and typically rule
out one of each pair of incompatible antibodies (the hypotheses).
Then do the assembly of a complete explanation.  This results in
assembly being polynomial.

If you send me your land mail address I can send you a copy of the
paper.  Or you can wait for the movie.  (Dean Allemang will present it
in Milan.)

-- mike

ARPA:  tanner@ohio-state
UUCP:  ...!cbosgd!osu-eddie!tanner