2
$\begingroup$

Is there any description logic where important decision problems (e.g. abox consistency or concept satisfiability) lie within NP with respect to their time complexity?

The well-researched family of $\mathcal{ALC}$-based logics might not work since even for $\mathcal{ALC}$, problems are PSpace-complete. Neither would the $\mathcal{EL}$ family since the problems are at least CoNP.

Some restriction thereof might work, though, although I couldn't find any so far.

$\endgroup$

2 Answers 2

1
$\begingroup$

Can see here https://www.w3.org/TR/owl2-profiles/#Computational_Properties for OWL-EL, OWL-QL and OWL-RL

$\endgroup$
0
$\begingroup$

Yes, but the only example I know is subsumption in FL$^-$, which actually is in P. On the other hand, subsumption in full FL is co-NP hard. A standard reference is Levesque and Brachman, Expressiveness and tractability in knowledge representation and reasoning. Here you can find more about FL$^-$, while these note are devoted to the computational complexity of satisfiability and subsumption in several description logics.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.