We investigate the complexity of several decision, enumeration and counting problems in axiom pinpointing in Description Logics. We prove hardness results that already hold for the propositional Horn fragment. We show that for this fragment, unless p = np, all minimal subsets of a given TBox that have a given consequence, i.e. MinAs, cannot be enumerated in a speci ed lexicographic order with polynomial delay. Moreover, we show that recognizing the set of all MinAs is at least as hard as recognizing the set of all minimal transversals of a given hypergraph, however whether this problem is intractable remains open. We also show that checking the existence of a MinA that does not contain any of the given sets of axioms, as well as checking the existence of a MinA that contains a speci ed axiom are both np-hard. In addition we show that counting all MinAs and counting the MinAs that contain a certain axiom are both #p-hard.
Introduction As the number and the size of DL-based ontologies grow, tools that support knowledge engineers in improving and maintaining the quality of these ontologies become more important. In real world applications often the knowledge engineer not only wants to know whether her knowledge base has a certain (unwanted) consequence or not, but also wants to know the reasons of this consequence. Even for knowledge bases of moderate size, nding explanations for a given consequence is not an easy task without getting support from an automated tool. The task of nding explanations for a given consequence, i.e., nding minimal subsets of the original knowledge base that have the given consequence is called axiom pinpointing in the literature.
Axiom pinpointing has been considered by several authors. In [
In the present paper we investigate the complexity of several decision,
enumeration and counting problems related to MinAs. Following [
Complexity of computing all MinAs In the present section we examine the complexity of computing all MinAs. The hardness results we show in this work actually already hold for the propositional Horn fragment HL. For this reason, from now on we are going to formulate our problems for HL TBoxes. Note that HL is a sublogic of E L, which implies that the lower bounds for the complexity found for HL also hold for E L and E L+. We start with formally de ning some basic notions.
De nition 1. Let T be an HL TBox and C and D be two HL concept descriptions such that C vT D. We call a set T 0 T a minimal axiom set or MinA for T w.r.t. C v D if C vT 0 D and it is minimal w.r.t. set inclusion. In this case we also say that T ' explains C v D.
Based on this, our problem is formulated as follows:
Input: An HL TBox T and a GCI C v D such that T j= C v D. Output: The set of all MinAs for T w.r.t. C v D. 2.1
In [
In the following we investigate whether it is possible to enumerate all MinAs in a speci ed lexicographic order with polynomial delay. The lexicographic order we will use is de ned as follows: De nition 2. Let the elements of a set S be linearly ordered. This order induces another linear strict order on P(S), which is called the lexicographic order. We say that a set R S is lexicographically smaller than a set T S where R 6= T if the rst element at which they disagree is in R.
Input: An HL TBox T , a GCI C v D such that T j= C v D, a set S T such that S j= C v D, and a linear order on T .
Question: Is S the rst MinA w.r.t. the lexicographic order induced by the given linear order?
Proof. The problem is in conp since if S is not the lexicographically rst MinA, a proof of this can be given by nondeterministically guessing a subset of T and verifying in polynomial time that it is a MinA that is lexicographically smaller than S.
In order to show conp-hardness, we are going to give a reduction from the
problem of checking whether a given maximal independent set is the
lexicographically last maximal independent set of a given graph. Recall that a maximal
independent set of a graph G = (V; E ) is a subset V 0 V of the vertices such
that no two vertices in V 0 are joined by an edge in E , and each vertex in V n V 0
is joined by an edge to some vertex in V 0. This problem has been shown to be
conp-complete in [
T := fPv v
l v2E;E2E
PE j v 2 V g [ f l PE v Ag; S := fPv v
l v2E;E2E
PE j v 2 (V n S)g [ f l PE v Ag:
Input: A graph G = (V; E), a maximal independent set S V , and a linear order on V .
Question: Is S the last maximal independent set w.r.t. the lexicographic order induced by the given linear order?
Let an instance of last-mis be given with the graph G = (V; E) and the maximal independent set S. From G and S we construct an instance of firstmina as follows: For every v 2 V we introduce a concept name Pv, for every edge E 2 E we introduce a concept name PE, and nally one more concept name A. Using these we construct the TBox E2E
E2E and the GCI dv2V Pv v A that obviously follows from T . Additionally, by using S we construct a set S T as: Note that T contains exactly jV j + 1 axioms. We order these axioms such that an axiom with premise Pv comes before the axiom with premise Pv0 if and only if the vertex v comes before the vertex v0 in the originally given linear order on V . Finally we place the axiom dE2E PE v A as the last one. It is easy to see that this construction indeed creates an instance of first-mina and the TBox T , as well as the MinA S and the GCI dv2V Pv v A can be created in time polynomial in the sizes of G and S. We claim that S is lexicographically the last maximal independent set if and only if S is the lexicographically rst MinA.
()) Assume S is the lexicographically last maximal independent set. Then V n S contains at least one vertex from every edge (i.e., it is a vertex cover), since otherwise S would not be an independent set. Thus every PE, for E 2 E, appears on the righthand side of at least one axiom in S. That is dv2V Pv vS dE2E PE, thus dv2V Pv vS A, i.e., S explains this axiom. Since S is maximal, V n S is minimal, and thus S is minimal, i.e., S is a MinA. Moreover, it is the lexicographically rst one since S is the lexicographically last maximal independent set.
(() Assume S is the lexicographically rst MinA. Then every PE, for E 2 E, appears on the righthand side of at least one axiom in S, since otherwise it would not be an explanation. That is, V nS contains at least one vertex from every edge. Then S contains at most one vertex from every edge, i.e., it is an independent set. Since S is minimal V n S is minimal, and thus S is maximal, i.e., S is a maximal independent set. Moreover it is the lexicographically last one since S is the lexicographically rst MinA. 2
Theorem 1 has the following consequence: Since generating the lexicographically rst MinA is already intractable, unless p = np, all MinAs cannot be enumerated in lexicographic order with polynomial delay.
Corollary 1. Unless p = np, there is no algorithm that enumerates MinAs in a given lexicographic order with polynomial delay.
Interestingly, it is easy to generate the lexicographically last MinA for a given TBox w.r.t. a given GCI. We start with the axioms in the speci ed order, and remove an axiom if the resulting set of axioms still explains the given GCI. Once we have scanned all axioms in this way, the resulting set of axioms is a MinA, and it is the lexicographically last one. For a TBox of size n, i. e. having n axioms, this operation requires at most n subsumption tests each of which can be done in polynomial time for E L and E L+. Nonetheless, it is still unclear whether this fact can be used to enumerate all MinAs in the reverse lexicographical order. 2.2
One other measure for analyzing the performance of enumeration algorithms
is to take into account not only the size of the input, but also the size of the
output. An algorithm is said to run in output polynomial time (or polynomial total
time) [
In the following we investigate whether mina-enum can be solved in output polynomial time. For solving this enumeration problem, the following decision problem has crucial importance:
Input: An HL TBox T , a GCI C v D such that T j= C v D, and T Question: Is T precisely the set of all MinAs of T w.r.t. C v D? As Proposition 1 below shows, if this problem cannot be decided in polynomial time, then unless p = np, mina-enum cannot be solved in output polynomial time.
Proposition 1. If all-minas cannot be decided in polynomial time, then unless p = np, mina-enum cannot be solved in output-polynomial time. Proof. Assume that we have an algorithm A that solves mina-enum in outputpolynomial time. Let its runtime be bounded by a polynomial p(IS; OS) where IS denotes the size of the input TBox and OS denotes the size of the output, i.e., the set of all MinAs.
In order to decide all-minas for an instance given by the TBox T , the GCI C v D, and a set T P(T ), we construct another algorithm A0 that works as follows: it runs A on T and C v D for at most p(jT j; jT j)-many steps. If A terminates within this many steps, then A0 compares the output of A with T and returns yes if and only if they are equal. If they are not equal, A0 returns no. If A has not yet terminated after p(jT j; jT j)-many steps, this implies that there is at least one MinA that is not contained in T , so A0 returns no. It is easy to see that the runtime of A0 is bounded by a polynomial in jT j and jT j, that is A0 decides all-minas in time polynomial in the size of the input. 2 P(T ).
The proposition shows that determining the complexity of all-minas is indeed crucial for determining the enumeration complexity of mina-enum. It is not di cult to see that all-minas is in conp. Given an instance of all-minas, a nondeterministic algorithm can guess a subset of T that is not in T , and in polynomial time verify that this is a MinA, thus T is not the set of all MinAs. In the following we show that all-minas is at least as hard as recognizing the set of all minimal transversals of a given hypergraph. However, whether it is conp-hard remains unfortunately open.
First we brie y recall some notions of hypergraphs. A hypergraph H = (V; E)
consists of a set of vertices V = fvi j 1 i ng, and a set of (hyper)edges
E = fEj j 1 j mg where Ej V . Following the convention in [
Input: Two hypergraphs H = (V; EH) and G = (V; EG).
Question: Is G the transversal hypergraph of H, i.e., does T r(H) = G hold?
trans-hyp is known to be in conp, but so far neither a polynomial time
algorithm has been found, nor has it been proved to be conp-hard. In a landmark
paper [
Proof. Let an instance of trans-hyp be given by the hypergraphs H = (V; EH) and G = (V; EG). From H and G we construct an instance of all-minas as follows: for every vertex v 2 V we introduce a concept name Pv, for every edge E 2 EH of H a concept name PE, and nally one additional concept name A. For a set of vertices F V , we de ne the TBox
TF := fPv v
l v2E;E2EH
PE j v 2 F g [ f
l PE v Ag: E2EH Using these we construct the TBox T := TV , a set of TBoxes T := fTF j F 2 EGg P(T ), and the GCI dv2V Pv v A that obviously follows from T .
It is easy to see that this construction indeed creates an instance of allminas, and the TBox T , as well as the set T and the GCI dv2V Pv v A can be constructed in time polynomial in the sizes of H and G. We claim that G is the transversal hypergraph of H if and only if T is precisely the set of all MinAs. Note that d PE v A is the only axiom in T that has A in its right-hand side; this impEl2ieEsHthat every MinA must contain this axiom. Hence, every MinA is of the form TF for some F V . To prove our claim, it su ces to show that a set of vertices F V is a minimal transversal of H if and only if the TBox TF is a MinA.
()) Assume that F is a minimal transversal of H. By de nition F satis es F \ E 6= ; for every E 2 EH . Then TF is an axiom set explaining the above GCI. Moreover, it is minimal since F is minimal. Thus, it is indeed a MinA for T w.r.t. dv2V Pv v A.
(() Now assume that TF is a MinA. Then for every PE (where E 2 EH) there is at least one axiom in TF with lefthand side Pv (where v 2 F and F 2 EG) such that Pv is subsumed by PE . That is F intersects every E 2 EH, i.e., F is a transversal. Moreover, it is minimal since the original set of axioms TF is a minimal axiom set.
It is not di cult to see that from the above it follows that G is the transversal hypergraph of H if and only if T := fTF j F 2 EG g is the set of all MinAs. 2 3
Preferred and unwanted axioms Next we consider the problem of computing MinAs that contain a preferred axiom and MinAs that do not contain some unwanted combination of axioms. First we investigate the problem of existence of a MinA that does not contain any of the given sets of axioms. This problem can be useful in applications where one wants to avoid certain combinations of axioms in the MinAs. It is de ned as follows:
Input: An HL TBox T , a GCI C v D such that T j= C v D, and T Question: Is there a MinA T 0 that satis es S 6 T 0 for every S 2 T ?
Proof. The problem is clearly in np. A nondeterministic algorithm for solving it rst guesses a T 0 T , then tests in polynomial time whether T 0 is a MinA that does not contain any of the S in T .
Hardness is shown by a reduction from the following np-hard problem [
Input: A hypergraph H = (V; E ).
Question: Is H 2-colorable, i.e., is there a W W \ E 6= ; and (V n W ) \ E 6= ;? V such that for all E 2 E , Let an instance of hypergraph 2-coloring be given with the hypergraph H = (V; E ). From H we construct an instance of add-mina as follows: just like in the construction in the proof of Theorem 2, we introduce a concept name Pv for every v 2 V , a concept name PE for every edge E 2 E , and nally one more concept name A. We also construct exactly the same TBox T and the GCI dv2V Pv v A constructed there. In addition to these, for an edge E 2 E we de ne the set
VE := fPv v
l v2F;F 2E
PF j v 2 Eg [ f l PF v Ag;
F 2E and using this construct the set
T := fVE j E 2 Eg: It is easy to see that the TBox T , the GCI above and the set T can be constructed in time polynomial in the size of H. We claim that H is 2-colorable if and only if there is a MinA T 0 for T w.r.t. dv2V Pv v A such that T 0 satis es S 6 T 0 for every S 2 T .
()) Assume H is 2-colorable. Then there is a W V such that W \ E 6= ; and (V n W ) \ E 6= ; for every E 2 E, i.e., both W and its complement are transversals of H. Assume w.l.o.g. that W is minimal. Using W we de ne the set TW := fPv v dv2E;E2E PE j v 2 W g [ fdE2E PE v Ag and claim that this is the MinA we are looking for. Since W is a transversal every PE, for E 2 E, appears on the righthand side of at least one axiom in TW . That is dv2V Pv vTW dE2E PE, thus dv2V Pv vTW A, i.e., TW explains this axiom. TW is minimal since W is minimal. Moreover, since V n W is also a transversal, every edge E 2 E contains at least one vertex v that is not in W . Thus, every VE 2 T contains at least one axiom Pv v dv2F;F 2E PF that is not in TW . That is TW is a MinA that is not a superset of any VE 2 T .
(() Assume there is a MinA T 0 that is not a superset of any VE 2 T . De ne the set WT 0 := fv j Pv v dv2E;E2E PE 2 T 0g. Since T 0 explains the constructed GCI, for every E 2 E it contains at least one axiom in whose righthandside PE occurs. That is, WT 0 intersects every E 2 E. Since T 0 is not a superset of any VE 2 T , every such VE contains at least one axiom that is not in T 0. This means that every E 2 E contains at least one vertex that is not in WT 0 . That is, V n WT 0 intersects every E 2 E. Thus we have shown that WT 0 is a 2-coloring of H. 2
Next we consider the dual problem, which is checking the existence of a MinA that contains a certain axiom. This problem can be useful in applications where one is interested in MinAs that contain a speci c axiom, and is known as the relevance problem:
Input: An HL TBox T , a GCI C v D such that T j= C v D, and an axiom t 2 T .
Question: Is there a MinA S of T w.r.t. C v D such that t 2 S?
If one could e ciently solve the relevance problem, then black-box techniques
for computing the set of all MinAs (see, e.g. [
Proof. The problem is clearly in np. A nondeterministic algorithm for solving it
rst guesses a subset of T , then tests in polynomial time whether it is a MinA
containing t. For showing hardness we are going to give a reduction from the
following np-complete problem in [
Input: Two sets of propositional variables H and M , a set T of de nite Horn clauses over H [ M , and a propositional variable p 2 H.
Question: Is there a minimal H0 H such that H0 [ T j= M and p 2 H0? Recall that a de nite Horn clause is a Horn clause with exactly one positive literal, i.e., the elements of T are formulae of the form V ! f , where G H [ M and f 2 H [ M . Given an instance of horgn2Grgelevance we construct an instance of mina-relevance as follows: for every propositional variable h 2 H we introduce a concept name Ph, for every propositional variable m 2 M we introduce a concept name Pm, and nally two more fresh concept names A and B. Using these we construct the TBox
T := fA v Ph j h 2 Hg [ f l Pg v Pf j ^ g ! f 2 T g [ f l Pm v Bg g2G g2G m2M where G H [ M and f 2 H [ M . Using A and B we construct the GCI A v B. This construction indeed creates an instance of mina-relevance and it can be done in polynomial time. We claim that there is a minimal H0 H such that H0 [ T j= M and p 2 H0 if and only if there is a MinA S of T w.r.t. A v B such that A v Pp 2 S.
()) Assume there is a minimal H0 H such that H0 [ T j= M and p 2 H0. Using H0 de ne the set TH0 := fA v Ph j h 2 H0g [ f l Pg v Pf j ^ g ! f 2 T g [ f l Pm v Bg: g2G g2G m2M TH0 explains A v B since H0 [ T j= M . It is minimal since H0 is minimal, and A v Pp 2 TH0 since p 2 H0.
(() Assume there is a MinA S such that A v Pp 2 S. Since it explains A v B it contains the axiom d dg2G Pg v Pf such that for everymm2M2PMm tvheBco,nccoenpttainnasmaexiPommsococfurtsheonfotrhme righthand side of at least one such axiom. Additionally S contains axioms of the form A v Ph such that A vS dm2M Pm. Then the set S = fh j A v Ph 2 Sg satis es S [ T j= M . Moreover p 2 S since A v Pp 2 S, and S is minimal since S is minimal. 2 4
Counting MinAs
In applications where one is interested in computing all MinAs, it might also
be useful to know in advance how many of them exist. Next we consider this
counting problem. It turns out that this is hard for the counting complexity
class #p [
Input: An HL TBox T and a GCI C v D such that T j= C v D. Output: The number of all MinAs of T w.r.t. C v D.
Proof. The problem is clearly in #p. Given an HL TBox T , a GCI C v D that follows from T and a candidate solution T 0 T , we can in polynomial time verify that T 0 is a MinA.
For showing #p-hardness, we are going to give a parsimonious reduction from
#hypergraph transversal, which is the problem of counting the minimal
transversals of a given hypergraph H. It has been shown to be #p-complete in
[
Instead of counting all MinAs, one can also try to count the MinAs that
contain a speci c axiom. If we are trying to explain an unwanted consequence,
the solution of this counting problem will allow us to detect axioms that are
most likely to be faulty, i. e. those that appear in the most MinAs. This idea has
been proposed in [
Input: An HL TBox T , a GCI C v D such that T j= C v D and an axiom t 2 T .
Output: The number of all MinAs of T w.r.t. C v D that contain t.
Proof. The problem is in #p since given an HL TBox T , a GCI C v D that follows from T an axiom t 2 T and a candidate solution T 0 T , we can in polynomial time verify that T 0 is a MinA and it contains t.
We show #p-hardness by a parsimonious reduction from #mina, which has been shown to be #p-complete above. Given an instance of #mina with the TBox T and the GCI A v B we construct the TBox T 0 := T [ S0, where S0 = fA v C; B u C v Dg, and C and D are two concept names not occurring in T . It is not di cult to see that a set S T is a MinA for T w.r.t. A v B if and only if S [ S0 is a MinA for T 0 w.r.t. A v D. Moreover, every MinA for T 0 w.r.t. A v D contains the axioms in S0. Thus, there are exactly as many MinAs for T w.r.t. A v B as there are for T 0 w.r.t. A v D containing the axiom A v C. 2
Concluding remarks and future work
We have analyzed the complexity of nding all the MinAs for a given HL TBox,
and some other related problems in axiom pinpointing. The bottom line of this
analysis is that axiom pinpointing is hard, even in this restricted setting, where
we can only express conjunctions and implications. Obviously, the hardness
results transfer to any logic more expressive than HL with GCIs. It is however
unclear whether better bounds can be obtained if we restrict our attention to
acyclic TBoxes, or to logics like DL-Lite [
One problem that remains open is the exact complexity of computing all
MinAs. In [
Another branch for future work refers to e ciently nding approximate solutions for the hard problems presented here. For instance nding an approximation to the total number of MinAs allows us at least to get an idea on how problematic is a given (unwanted) consequence. Alternatively, a set of axioms that explains a given consequence but is not necessarily minimal, can be helpful for a better understanding of the given consequence.