document.155

5 Computational Properties

This section describes the computational complexity of the most relevant reasoning problems of the languages defined in this document. For an introduction to computational complexity, please refer to a textbook on complexity such as [Papadimitriou]. The reasoning problems considered here are ontology consistency, class expression satisfiability, class expression subsumption, instance checking, and (Boolean) conjunctive query answering [OWL 2 Direct Semantics]. When evaluating complexity, the following parameters will be considered:

Data Complexity: the complexity measured with respect to the total size of the assertions in the ontology.
Taxonomic Complexity: the complexity measured with respect to the total size of the axioms in the ontology.
Query Complexity: the complexity measured with respect to the total size of the query.
Combined Complexity: the complexity measured with respect to both the size of the axioms, the size of the assertions, and, in the case of conjunctive query answering, the size of the query as well.
Table 10 summarizes the known complexity results for OWL 2 under both RDF and the direct semantics, OWL 2 EL, OWL 2 QL, OWL 2 RL, and OWL 1 DL. The meaning of the entries is as follows:

Decidability open means that it is not known whether this reasoning problem is decidable at all.
Decidable, but complexity open means that decidability of this reasoning problem is known, but not its exact computational complexity. If available, known lower bounds are given in parenthesis; for example, (NP-Hard) means that this problem is at least as hard as any other problem in NP.
X-complete for X one of the complexity classes explained below indicates that tight complexity bounds are known — that is, the problem is known to be both in the complexity class X (i.e., an algorithm is known that only uses time/space in X) and hard for X (i.e., it is at least as hard as any other problem in X). The following is a brief sketch of the classes used in this table, from the most complex one down to the simplest ones.
2NEXPTIME is the class of problems solvable by a nondeterministic algorithm in time that is at most double exponential in the size of the input (i.e., roughly 22n, for n the size of the input).
NEXPTIME is the class of problems solvable by a nondeterministic algorithm in time that is at most exponential in the size of the input (i.e., roughly 2n, for n the size of the input).
PSPACE is the class of problems solvable by a deterministic algorithm using space that is at most polynomial in the size of the input (i.e., roughly nc, for n the size of the input and c a constant).
NP is the class of problems solvable by a nondeterministic algorithm using time that is at most polynomial in the size of the input (i.e., roughly nc, for n the size of the input and c a constant).
PTIME is the class of problems solvable by a deterministic algorithm using time that is at most polynomial in the size of the input (i.e., roughly nc, for n the size of the input and c a constant). PTIME is often referred to as tractable, whereas the problems in the classes above are often referred to as intractable.
LOGSPACE is the class of problems solvable by a deterministic algorithm using space that is at most logarithmic in the size of the input (i.e., roughly log(n), for n the size of the input and c a constant). NLOGSPACE is the non-deterministic version of this class.
AC0 is a proper subclass of LOGSPACE and defined not via Turing Machines, but via circuits: AC0 is the class of problems definable using a family of circuits of constant depth and polynomial size, which can be generated by a deterministic Turing machine in logarithmic time (in the size of the input). Intuitively, AC0 allows us to use polynomially many processors but the run-time must be constant. A typical example of an AC0 problem is the evaluation of first-order queries over databases (or model checking of first-order sentences over finite models), where only the database (first-order model) is regarded as the input and the query (first-order sentence) is assumed to be fixed. The undirected graph reachability problem is known to be in LogSpace, but not in AC0.
The results below refer to the worst-case complexity of these reasoning problems and, as such, do not say that implemented algorithms necessarily run in this class on all input problems, or what space/time they use on some/typical/certain kind of problems. For X-complete problems, these results only say that a reasoning algorithm cannot use less time/space than indicated by this class on all input problems.

Table 10. Complexity of the Profiles
Language	Reasoning Problems	Taxonomic Complexity	Data Complexity	Query Complexity	Combined Complexity
OWL 2
RDF-Based Semantics	Ontology Consistency, Class Expression Satisfiability,
Class Expression Subsumption, Instance Checking,
Conjunctive Query Answering	Undecidable	Undecidable	Undecidable	Undecidable
OWL 2
Direct Semantics	Ontology Consistency, Class Expression Satisfiability,
Class Expression Subsumption, Instance Checking	2NEXPTIME-complete (NEXPTIME if property hierarchies are bounded)	Decidable, but complexity open
(NP-Hard)	Not Applicable	2NEXPTIME-complete (NEXPTIME if property hierarchies are bounded)
Conjunctive Query Answering	Decidability open	Decidability open	Decidability open	Decidability open
OWL 2 EL	Ontology Consistency, Class Expression Satisfiability,
Class Expression Subsumption, Instance Checking	PTIME-complete	PTIME-complete	Not Applicable	PTIME-complete
Conjunctive Query Answering	PTIME-complete	PTIME-complete	NP-complete	PSPACE-complete
OWL 2 QL	Ontology Consistency, Class Expression Satisfiability,
Class Expression Subsumption, Instance Checking,	NLogSpace-complete	In AC0	Not Applicable	NLogSpace-complete
Conjunctive Query Answering	NLogSpace-complete	In AC0	NP-complete	NP-complete
OWL 2 RL	Ontology Consistency, Class Expression Satisfiability,
Class Expression Subsumption, Instance Checking	PTIME-complete	PTIME-complete	Not Applicable	PTIME-complete
Conjunctive Query Answering	PTIME-complete	PTIME-complete	NP-complete	NP-complete
OWL 1 DL	Ontology Consistency, Class Expression Satisfiability,
Class Expression Subsumption, Instance Checking	NEXPTIME-complete	Decidable, but complexity open
(NP-Hard)	Not Applicable	NEXPTIME-complete
Conjunctive Query Answering	Decidability open	Decidability open	Decidability open	Decidability open