The complexity of path-based defeasible inheritance

Touretzky (1984) proposed a formalism for nonmonotonic multiple inheritance reasoning which is sound in the presence of ambiguities and redundant links. We show that Touretzky's inheritance notion is NPhard, and thus, provided P#NP, computationally intractable. This result holds even when one only considers unambiguous, totally acyclic inheritance networks. A direct consequence of this result is that the conditioning strategy proposed by Touretzky to allow for fast parallel inference is also intractable. Therefore, it follows that nonmonotonic multiple inheritance hierarchies, although compact representations, may not allow for efficient retrieval of information as has been suggested in attempts to use such hierarchies, e.g., in NETL (Fahlman 1979). We also analyze the influence of various design choices made by Touretzky. We show that all versions of downward (coupled) inheritance, i.e., on-path or off-path preemption and skeptical or credulous reasoning, are intractable. However, tractability can be achieved when using upward (decoupled) inheritance.