THE COMPLEXITY OF PATH-BASED DEFEASIBLE INHERITANCE

Touretzky [22] proposed a formalism for nonmonotonic multiple inherita nce reasoning which is sound in the presence of ambiguities and redund ant links. We show that Touretzky's inheritance notion is NP-hard, and thus, provided P not-equal NP, computationally intractable. This resu lt holds even when one only considers unambiguous, totally acyclic inh eritance networks. A direct consequence of this result is that the con ditioning strategy proposed by Touretzky to allow for fast parallel in ference is also intractable. We also analyze the influence of various design choices made by Touretzky. We show that all versions of so-call ed downward inheritance, i.e., on-path or off-path preemption and skep tical or credulous reasoning, are intractable. However, on the positiv e side, tractability can be achieved when using upward inheritance. Fi nally, we consider the problem of determining what holds in all extens ions of an ambiguous inheritance network. Without any preemption-corre sponding to a very cautious form of inheritance-this problem is tracta ble, but when allowing even the most basic forms of preemption, it bec omes intractable.