  One of the main reasons to employ a description logic such as EL or EL++ is
the fact that it has efficient, polynomial-time algorithmic properties such as
deciding consistency and inferring subsumption. However, simply by adding
negation of concepts to it, we obtain the expressivity of description logics
whose decision procedure is {ExpTime}-complete. Similar complexity explosion
occurs if we add probability assignments on concepts. To lower the resulting
complexity, we instead concentrate on assigning probabilities to Axioms (GCIs).
We show that the consistency detection problem for such a probabilistic
description logic is NP-complete, and present a linear algebraic deterministic
algorithm to solve it, using the column generation technique. We also examine
and provide algorithms for the probabilistic extension problem, which consists
of inferring the minimum and maximum probabilities for a new axiom, given a
consistent probabilistic knowledge base.
