Name
Abstract | ||
|---|---|---|
Abduction is a fundamental form of nonmonotonic reasoning that aims at finding explanations for observed manifestations. Applications of this process range from car configuration to medical diagnosis. We study here its computational complexity in the case where the application domain is described by a propositional theory built upon a fixed constraint language and the hypotheses and manifestations are described by sets of literals. We show that depending on the language the problem is either polynomial-time solvable, NP-complete, or ΣP2-complete. In particular, we show that under the assumption P≠NP, only languages that are affine of width 2 have a polynomial algorithm, and we exhibit very weak conditions for NP-hardness. |
Year | Venue | Keywords |
|---|---|---|
2005 | IJCAI | observed manifestation,nonmonotonic reasoning,application domain,fixed constraint language,assumption p,fundamental form,polynomial algorithm,computational complexity,propositional abduction,medical diagnosis,car configuration,polynomial time |
Field | DocType | Citations |
Affine transformation,Discrete mathematics,Computer science,Application domain,Non-monotonic logic,Almost surely,Polynomial algorithm,Medical diagnosis,Computational complexity theory | Conference | 10 |
PageRank | References | Authors |
0.56 | 19 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gustav Nordh | 1 | 121 | 10.40 |
| Bruno Zanuttini | 2 | 289 | 25.43 |