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.