Axiom Pinpointing is Hard Rafael Peñaloza and Barış Sertkaya? Theoretical Computer Science TU Dresden, Germany {penaloza,sertkaya}@tcs.inf.tu-dresden.de Abstract. We investigate the complexity of several decision, enumera- tion 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, can- not be enumerated in a specified 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 hy- pergraph, 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 specified 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. 1 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, finding explanations for a given consequence is not an easy task without getting support from an automated tool. The task of finding explanations for a given consequence, i.e., finding 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 [18] Schlobach and Cornet have described an extension of the tableau-based satisfiability al- gorithm for ALC that given an ALC knowledge base and a consequence of this knowledge base computes all minimal subsets of the original knowledge base that have the given consequence. The same problem had been addressed earlier in [1] in the context of extending DLs by default rules. Later in [15] Parsia et al. have extended the approach in [18] to more expressive DLs, and in [14] Lee et al. have extended the approach in [1] to ALC knowledge bases with GCIs. In contrast to ? Supported by the German Research Foundation (DFG) under grant BA 1122/12-1 these works on axiom pinpointing in expressive DLs, in [2] Baader et al. have ad- dressed axiom pinpointing in the less expressive DL EL+ . They have investigated the complexity of finding minimal subsets of a given EL+ TBox (there called MinAs) that have a given consequence. They have shown that checking the exis- tence of a MinA within a specified cardinality bound is np-complete. Moreover, they have shown that a given consequence can have exponentially many MinAs in a given EL+ TBox. Given this fact, it is definitely not possible to compute all MinAs in polynomial time. Baader et al. have considered this problem in a setting where the TBox has a so-called static part which is always present, and a refutable part from which MinAs are computed. They have shown that in this setting computing all MinAs cannot be performed in output polynomial time unless p = np. In fact, all these hardness results are shown for the propositional Horn fragment (there called HL), that allows for only conjunction and GCIs. In the present paper we investigate the complexity of several decision, enu- meration and counting problems related to MinAs. Following [2], we show our hardness results for the logic HL. First we examine whether MinAs can be enumerated in a specified lexicographic order with polynomial delay. It turns out that even for HL already generating the lexicographically first MinA is intractable, thus unless p = np, MinAs cannot be enumerated in a specified lexi- cographic order with polynomial delay. Next we examine whether all MinAs can be computed in output polynomial time without the static part considered in the setting in [2]. We show that for this setting recognizing the set of all MinAs is at least as hard as recognizing the set of all minimal transversals of a given hypergraph, which is a prominent open problem [8] in hypergraph theory [4]. However, whether this problem is intractable remains open. Next we investigate the problem of existence of a MinA that does not contain any of the given sets of axioms. This problem, which can be useful in practical applications where one wants to avoid certain combinations of axioms in the MinAs, turns out to be np-hard. We also consider the problem of checking the existence of a MinA that contains a specified axiom. We show that this problem is also np-hard. Finally, we show that both counting all MinAs and counting the MinAs that contain a certain axiom are #p-hard problems. 2 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 EL, which implies that the lower bounds for the complexity found for HL also hold for EL and EL+ . We start with formally defining some basic notions. Definition 1. Let T be an HL TBox and C and D be two HL concept descrip- tions 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: Problem: mina-enum Input: An HL TBox T and a GCI C v D such that T |= C v D. Output: The set of all MinAs for T w.r.t. C v D. 2.1 Enumerability with polynomial delay In [2] it has been shown that there can be exponentially many MinAs for a given HL TBox w.r.t. a given consequence of this TBox. Given this fact, it is definitely not possible to solve mina-enum in polynomial time. In complexity theory, for analyzing the performance of enumeration algorithms where the number of solu- tions can be exponential in the size of the input, one considers other measures. One such measure is the time the algorithm spends between two consequent solutions. An algorithm is said to run with polynomial delay [13] if the time until the first solution is generated, and thereafter the time between any two consecutive solutions is bounded by a polynomial in the size of the input. In the following we investigate whether it is possible to enumerate all MinAs in a specified lexicographic order with polynomial delay. The lexicographic order we will use is defined as follows: Definition 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 first element at which they disagree is in R. Problem: first-mina Input: An HL TBox T , a GCI C v D such that T |= C v D, a set S ⊆ T such that S |= C v D, and a linear order on T . Question: Is S the first MinA w.r.t. the lexicographic order induced by the given linear order? Theorem 1. first-mina is conp-complete. Proof. The problem is in conp since if S is not the lexicographically first 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 lexicograph- ically 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 \ V 0 is joined by an edge to some vertex in V 0 . This problem has been shown to be conp-complete in [13]. Problem: last maximal independent set (last-mis) 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 first- mina as follows: For every v ∈ V we introduce a concept name Pv , for every edge E ∈ E we introduce a concept name PE , and finally one more concept name A. Using these we construct the TBox l l T := {Pv v PE | v ∈ V } ∪ { PE v A}, v∈E,E∈E E∈E d and the GCI v∈V Pv v A that obviously follows from T . Additionally, by using S we construct a set S ⊆ T as: l l S := {Pv v PE | v ∈ (V \ S)} ∪ { PE v A}. v∈E,E∈E E∈E Note that T contains exactly |V | + 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 thed vertex v 0 in the originally given linear order on V . Finally we place the axiom E∈E PE v A as the last one. It is easy to see that this construction indeed creates an instance d of first-mina and the TBox T , as well as the MinA S and the GCI v∈V 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 first MinA. (⇒) Assume S is the lexicographically last maximal independent set. Then V \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 d PE , for E ∈ E, d appears on thedrighthand side of at least one axiom in S. That is v∈V Pv vS E∈E PE , thus v∈V Pv vS A, i.e., S explains this axiom. Since S is maximal, V \ S is minimal, and thus S is minimal, i.e., S is a MinA. Moreover, it is the lexico- graphically first one since S is the lexicographically last maximal independent set. (⇐) Assume S is the lexicographically first MinA. Then every PE , for E ∈ E, appears on the righthand side of at least one axiom in S, since otherwise it would not be an explanation. That is, V \S 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 \ 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 first MinA. 2 Theorem 1 has the following consequence: Since generating the lexicograph- ically first 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 specified 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 EL and EL+ . Nonetheless, it is still unclear whether this fact can be used to enumerate all MinAs in the reverse lexicographical order. 2.2 Computability in output polynomial time 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) [13] if it outputs all solutions in time polynomial in the size of the input and the output. One advantage of an output polynomial algorithm is that it runs in polynomial time (in the size of the input) when there are only polynomially many solutions. 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: Problem: all-minas Input: An HL TBox T , a GCI C v D such that T |= C v D, and T ⊆ P(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 output- polynomial 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(|T |, |T |)-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(|T |, |T |)-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 |T | and |T |, that is A0 decides all-minas in time polynomial in the size of the input. 2 The proposition shows that determining the complexity of all-minas is in- deed crucial for determining the enumeration complexity of mina-enum. It is not difficult 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 briefly recall some notions of hypergraphs. A hypergraph H = (V, E) consists of a set of vertices V = {vi | 1 ≤ i ≤ n}, and a set of (hyper)edges E = {Ej | 1 ≤ j ≤ m} where Ej ⊆ V . Following the convention in [4], we assume that the set of edges as well as the set of vertices is nonempty, and the union of all edges yields the vertex set. A set W ⊆ V is called a transversal of H if it intersects all edges of H, i.e., ∀E ∈ E. E ∩W 6= ∅. A transversal is called minimal if no proper subset of it is a transversal. The set of all minimal transversals of H constitute another hypergraph on V called the transversal hypergraph of H, which is denoted by T r(H). Generating T r(H) is an important problem which has applications in many fields of computer science (see e.g. [9]). The well-known decision problem associated to this computation problem is defined as follows: Problem: transversal hypergraph (trans-hyp) 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 algo- rithm has been found, nor has it been proved to be conp-hard. In a landmark paper [10] Fredman and Khachiyan proved that trans-hyp can be solved in no(log n) time, which implies that this problem is most likely not conp-hard. It is conjectured that this problem, together with several computationally equivalent problems, forms a class properly contained between p and conp [10]. Theorem 2. all-minas is trans-hyp-hard. 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 ∈ V we introduce a concept name Pv , for every edge E ∈ EH of H a concept name PE , and finally one additional concept name A. For a set of vertices F ⊆ V , we define the TBox l l TF := {Pv v PE | v ∈ F } ∪ { PE v A}. v∈E,E∈EH E∈EH Using these we construct the d TBox T := TV , a set of TBoxes T := {TF | F ∈ EG } ⊆ P(T ), and the GCI v∈V Pv v A that obviously follows from T . It is easy to see that this construction indeed creates d an instance of all- minas, and the TBox T , as well as the set T and the GCI v∈V Pv v A can be constructed in time polynomial in the sizes of H and G. We claim that G is the transversaldhypergraph of H if and only if T is precisely the set of all MinAs. Note that E∈EH PE v A is the only axiom in T that has A in its right-hand side; this implies that every MinA must contain this axiom. Hence, every MinA is of the form TF for some F ⊆ V . To prove our claim, it suffices 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 definition F satisfies F ∩ E 6= ∅ for every E ∈ EH . Then TF is an axiom set explaining the above GCI. Moreover, d it is minimal since F is minimal. Thus, it is indeed a MinA for T w.r.t. v∈V Pv v A. (⇐) Now assume that TF is a MinA. Then for every PE (where E ∈ EH ) there is at least one axiom in TF with lefthand side Pv (where v ∈ F and F ∈ EG ) such that Pv is subsumed by PE . That is F intersects every E ∈ 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 difficult to see that from the above it follows that G is the transversal hypergraph of H if and only if T := {TF | F ∈ EG } 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 defined as follows: Problem: add-mina Input: An HL TBox T , a GCI C v D such that T |= C v D, and T ⊆ P(T ). Question: Is there a MinA T 0 that satisfies S 6⊆ T 0 for every S ∈ T ? Theorem 3. add-mina is np-complete. Proof. The problem is clearly in np. A nondeterministic algorithm for solving it first 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 [12]: Problem: hypergraph 2-coloring Input: A hypergraph H = (V, E). Question: Is H 2-colorable, i.e., is there a W ⊆ V such that for all E ∈ E, W ∩ E 6= ∅ and (V \ W ) ∩ E 6= ∅? 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 ∈ V , a concept name PE for every edge E ∈ E, and finally one more d concept name A. We also construct exactly the same TBox T and the GCI v∈V Pv v A constructed there. In addition to these, for an edge E ∈ E we define the set l l VE := {Pv v PF | v ∈ E} ∪ { PF v A}, v∈F,F ∈E F ∈E and using this construct the set T := {VE | E ∈ E}. 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 d H. We claim that H is 2-colorable if and only if there is a MinA T 0 for T w.r.t. v∈V Pv v A such that T 0 satisfies S 6⊆ T 0 for every S ∈ T . (⇒) Assume H is 2-colorable. Then there is a W ⊆ V such that W ∩ E 6= ∅ and (V \ W ) ∩ E 6= ∅ for every E ∈ E, i.e., both W and its complement are transversals of H. Assume d w.l.o.g. that W is minimal. d Using W we define the set TW := {Pv v v∈E,E∈E PE | v ∈ W } ∪ { E∈E PE v A} and claim that this is the MinA we are looking for. Since W is a transversal every PE , for E ∈ E, appearsd on the righthand d d side of at least one axiom in TW . That is v∈V P v v T W E∈E P E , thus v∈V Pv vTW A, i.e., TW explains this axiom. TW is minimal since W is minimal. Moreover, since V \ W is also a transversal, every edge E ∈ E contains at least one vertex d v that is not in W . Thus, every VE ∈ T contains at least one axiom Pv v v∈F,F ∈E PF that is not in TW . That is TW is a MinA that is not a superset of any VE ∈ T . (⇐) Assume there is adMinA T 0 that is not a superset of any VE ∈ T . Define the set WT 0 := {v | Pv v v∈E,E∈E PE ∈ T 0 }. Since T 0 explains the constructed GCI, for every E ∈ E it contains at least one axiom in whose righthandside PE occurs. That is, WT 0 intersects every E ∈ E. Since T 0 is not a superset of any VE ∈ T , every such VE contains at least one axiom that is not in T 0 . This means that every E ∈ E contains at least one vertex that is not in WT 0 . That is, V \ WT 0 intersects every E ∈ 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 specific axiom, and is known as the relevance problem: Problem: mina-relevance Input: An HL TBox T , a GCI C v D such that T |= C v D, and an axiom t∈T. Question: Is there a MinA S of T w.r.t. C v D such that t ∈ S? If one could efficiently solve the relevance problem, then black-box techniques for computing the set of all MinAs (see, e.g. [3, 20]) based on Reiter’s Hitting Set Tree algorithm [16] could benefit from Rymon’s further optimizations [17]. As we will show next, this problem is also np-hard. Theorem 4. mina-relevance is np-complete. Proof. The problem is clearly in np. A nondeterministic algorithm for solving it first 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 [11, 7]: Problem: horn-relevance Input: Two sets of propositional variables H and M , a set T of definite Horn clauses over H ∪ M , and a propositional variable p ∈ H. Question: Is there a minimal H 0 ⊆ H such that H 0 ∪ T |= M and p ∈ H 0 ? Recall that a definite Horn clause is a Horn clause with V exactly one positive literal, i.e., the elements of T are formulae of the form g∈G g → f , where G ⊆ H ∪ M and f ∈ H ∪ M . Given an instance of horn relevance we construct an instance of mina-relevance as follows: for every propositional variable h ∈ H we introduce a concept name Ph , for every propositional variable m ∈ M we introduce a concept name Pm , and finally two more fresh concept names A and B. Using these we construct the TBox l ^ l T := {A v Ph | h ∈ H} ∪ { P g v Pf | g → f ∈ T} ∪ { Pm v B} g∈G g∈G m∈M where G ⊆ H ∪ M and f ∈ 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 H 0 ⊆ H such that H 0 ∪ T |= M and p ∈ H 0 if and only if there is a MinA S of T w.r.t. A v B such that A v Pp ∈ S. (⇒) Assume there is a minimal H 0 ⊆ H such that H 0 ∪ T |= M and p ∈ H 0 . Using H 0 define the set l ^ l TH 0 := {A v Ph | h ∈ H 0 } ∪ { Pg v P f | g → f ∈ T} ∪ { Pm v B}. g∈G g∈G m∈M TH 0 explains A v B since H 0 ∪ T |= M . It is minimal since H 0 is minimal, and A v Pp ∈ TH 0 since p ∈ H 0 . (⇐) Assume there is a MinA d S such that A v Pp ∈ S. Since it explains A d v B it contains the axiom m∈M Pm v B, contains axioms of the form g∈G P g v P f such that for every m ∈ M the concept name Pm occurs on the righthand side of at least one such d axiom. Additionally S contains axioms of the form A v Ph such that A vS m∈M Pm . Then the set S = {h | A v Ph ∈ S} satisfies S ∪ T |= M . Moreover p ∈ S since A v Pp ∈ 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 [21], which is defined as the class of functions counting the number of accepting paths of nondeterministic Turing machines. Problem: #mina Input: An HL TBox T and a GCI C v D such that T |= C v D. Output: The number of all MinAs of T w.r.t. C v D. Theorem 5. #mina is #p-complete. 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 [6]. In the reduction, from a given hypergraph H we construct the same TBox and the GCI constructed in the proof of Theorem 2. Note that this construction establishes d a bijection between the minimal transversals of H and MinAs of T w.r.t. v∈V Pv v A. That d is, a W ⊆ V is a minimal d transversal of H if and only if the set T := {Pv v v∈E,E∈EH PE | v ∈ W } ∪ { E∈EH PE v A} defined using W is a MinA. That is, this construction preserves the number of solutions, i.e., it is parsimonious. 2 Instead of counting all MinAs, one can also try to count the MinAs that contain a specific 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 [19] as a heuristic for correcting an error while minimizing the changes in the set of axioms. Problem: #mina-relevance Input: An HL TBox T , a GCI C v D such that T |= C v D and an axiom t∈T. Output: The number of all MinAs of T w.r.t. C v D that contain t. Theorem 6. #mina-relevance is #p-complete. Proof. The problem is in #p since given an HL TBox T , a GCI C v D that follows from T an axiom t ∈ 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 = {A v C, B u C v D}, and C and D are two concept names not occurring in T . It is not difficult 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 5 Concluding remarks and future work We have analyzed the complexity of finding 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 re- sults 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 [5] in which conjunction is not allowed on the lefthand side of the axioms. One problem that remains open is the exact complexity of computing all MinAs. In [2] it was shown that if we allow for an irrefutable portion of the TBox, then there cannot be an algorithm that outputs all MinAs in output polynomial time. Here we show that if all axioms are refutable then this problem is at least as hard as generating the minimal transversals of a given hypergraph. However, whether it is intractable remains open. As future work, we are going to work on determining whether this problem is intractable or it is computationally equivalent to generating minimal transversals. Another branch for future work refers to efficiently finding approximate so- lutions for the hard problems presented here. For instance finding an approxi- mation 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. References 1. F. Baader and B. Hollunder. Embedding defaults into terminological representation systems. Journal of Automated Reasoning, 14:149–180, 1995. 2. F. Baader, R. Peñaloza, and B. Suntisrivaraporn. Pinpointing in the description logic EL+ . In J. Hertzberg, M. Beetz, and R. Englert, editors, Proceedings of the 30th German Conference on Artificial Intelligence (KI2007), volume 4667 of Lecture Notes in Artificial Intelligence, pages 52–67. Springer-Verlag, 2007. 3. F. Baader and B. Suntisrivaraporn. Debugging SNOMED CT using axiom pin- pointing in the description logic EL+ . In Proceedings of the International Con- ference on Representing and Sharing Knowledge Using SNOMED (KR-MED’08), Phoenix, Arizona, 2008. 4. C. Berge. Hypergraphs. Elsevier Science Publishers B.V. (North Holland), 1989. 5. D. Calvanese, G. D. Giacomo, M. Lenzerini, R. Rosati, and G. Vetere. DL-Lite: Practical reasoning for rich DLs. In Proceedings of the 2004 Description Logic Workshop (DL 2004), volume 104 of CEUR Electronic Workshop Proceedings, http://ceur-ws.org/, 2004. 6. A. Durand and M. Hermann. On the counting complexity of propositional circum- scription. Information Processing Letters, 106(4):164–170, 2008. 7. T. Eiter and G. Gottlob. The complexity of logic-based abduction. Journal of the ACM, 42(1):3–42, 1995. 8. T. Eiter and G. Gottlob. Identifying the minimal transversals of a hypergraph and related problems. SIAM Journal on Computing, 24(6):1278–1304, 1995. 9. T. Eiter and G. Gottlob. Hypergraph transversal computation and related prob- lems in logic and AI. In S. Flesca, S. Greco, N. Leone, and G. Ianni, editors, Proceedings of the European Conference on Logics in Artificial Intelligence (JELIA 2002), volume 2424 of Lecture Notes in Computer Science, pages 549–564. Springer- Verlag, 2002. 10. M. L. Fredman and L. Khachiyan. On the complexity of dualization of monotone disjunctive normal forms. Journal of Algorithms, 21(3):618–628, 1996. 11. G. Friedrich, G. Gottlob, and W. Nejdl. Hypothesis classification, abductive di- agnosis and therapy. In G. Gottlob and W. Nejdl, editors, Proceedings of the International Workshop on Expert Systems in Engineering, Principles and Appli- cations, volume 462 of Lecture Notes in Computer Science, pages 69–78, Viena, Austria, 1990. Springer-Verlag. 12. M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Company, New York, NY, USA, 1990. 13. D. S. Johnson, M. Yannakakis, and C. H. Papadimitriou. On generating all maxi- mal independent sets. Information Processing Letters, 27(3):119–123, 1988. 14. K. Lee, T. Meyer, and J. Z. Pan. Computing maximally satisfiable terminologies for the description logic ALC with GCIs. In B. Parsia, U. Sattler, and D. Toman, editors, Proceedings of the International Workshop on Description Logics (DL’06), Lake District, UK, 2006. 15. B. Parsia, E. Sirin, and A. Kalyanpur. Debugging OWL ontologies. In A. Ellis and T. Hagino, editors, Proceedings of the 14th international conference on World Wide Web (WWW 2005), pages 633–640. ACM, 2005. 16. R. Reiter. A theory of diagnosis from first principles. Artificial Intelligence, 32(1):57–95, 1987. 17. R. Rymon. Search through systematic set enumeration. In B. Nebel, C. Rich, and W. Swartout, editors, Proceedings of the International Conference on the Principles of Knowledge Representation and Reasoning (KR’92), pages 539–550, Cambridge, MA, USA, 1992. 18. S. Schlobach and R. Cornet. Non-standard reasoning services for the debugging of description logic terminologies. In G. Gottlob and T. Walsh, editors, Proceed- ings of the Eighteenth International Joint Conference on Artificial Intelligence (IJ- CAI’03), pages 355–362. Morgan Kaufmann, 2003. 19. S. Schlobach, Z. Huang, R. Cornet, and F. Harmelen. Debugging incoherent ter- minologies. Journal of Automated Reasoning, 39(3):317–349, 2007. 20. B. Suntisrivaraporn, G. Qi, Q. Ji, and P. Haase. A modularization-based ap- proach to finding all justifications for OWL DL entailments. In J. Domingue and C. Anutariya, editors, Proceedings of the 3rd Asian Semantic Web Confer- ence (ASWC’08), volume 5367 of Lecture Notes in Computer Science, pages 1–15. Springer-Verlag, 2008. 21. L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189–201, 1979.