--- title: "The Complexity of Theory Revision" authors: - "Russell Greiner" doi: "" url: "https://ijcai.org/proceedings/1995/150" pdf: "https://ijcai.org/proceedings/1995/0150.pdf" venue: "Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence" year: 1995 pages: "1162-1167" track: "Learning" keywords: --- # The Complexity of Theory Revision Russell Greiner *Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence*, pages 1162-1167. ## Abstract A knowledge-based system uses its database (a.k.a. its "theory") to produce answers to the queries it receives. Unfortunately, these answers may be incorrect if the underlying theory is faulty. Standard "theory revision" systems use a given set of "labeled queries" (each a query paired with its correct answer) to transform the given theory, by adding and/or deleting either rules and/or antecedents, into a related theory that is as accurate as possible. After formally defining the theory revision task and bounding its sample complexity, this paper addresses the task's computational complexity. It first proves that, unless P = NP, no polynomial time algorithm can identify the optimal theory, even given the exact distribution of queries, except in the most trivial of si.t~a tions. It also shows that, except in such tnvial situations, no polynomial-time algorithm can produce a theory whose inaccuracy is even close (i.e., within a particular polynomial factor) to optimal. These results justify the standard practice of hill-climbing to a locally-optimal theory, based on a given set of labeled samples. ## Full text ## 1 Introduction There are many fielded knowledge-based systems, rang­ ing from expert systems and logic programs to produc­ tion systems and database management systems. [Lev84]. Each such system uses its database of general mforma­ tion (a.k.a. its "theory") to produce an .an~wer. to each given query; this can correspo~d to retnevmg I,~forma­ tion from a database (e.g., findmg X such that (makes acme X) & (color X red)") or to providing a diagno­ sis or repair, based on a given set of sympt.oms. Unfortu­ nately, these responses may be incorrect If the underly­ ing theory includes erroneous informa~ion. If w~ observe that some answers are incorrect (e.g., If the patient does not get better, or the proposed repair does not correct the device's faults), we can then ask a human expert to supply the correct answer. Theory revisio.n is the p~o­ cess of using such correctly-answered quenes to mod1fy the initial theory, to produce a new theory that is m~re accurate; i.e., which will not make those mistakes agam, while remaining correct on the other queries. *I gratefully acknowledge receiving helpful comments from George Drastal, R. Bharat Rao, Narendra Gupta, Tom Han: cock, Sheila Mcllraith, Edoardo Amaldi, Dan Roth and Rom Khardon. Most theory revision algorithms use a set of transfor­ mations to hill-climb through successive theories, until reaching a theory whose accuracy is (locally) optimal, based on a set of correctly-answered queries; cj., [Pol85; MB88; Coh90; OM94; WP93; CS90; LDRG94]. This re­ port addresses the obvious question: Is there a b:tter approach, which will directly yield the globally optimal theory? Section 2 first states the theory revision objective more precisely: as finding the theory with the highest accu­ racy from the space of theories formed by applying a se­ quence of transformations to a give~ initial the?ry; ~ere, each transform involves either addmg or deletmg either a rule or an antecedent. It also proves that a polyno­ mial number of training "labeled queries" (each a spe­ cific query paired with its correct answer) is .suffic.ient; i.e., they provide the information needed to Identify a transformation-sequence that will transform the given theory into a new theory whose accuracy is arbitrarily close to optimal, with arbitrarily high probability .. Sec­ tion 3 then addresses the computational complexity of the task of finding the optimal (or even near-optimal) revised theory. It first proves that the task of comput­ ing the optimal theory within this space of theories is intractable, even in trivial contexts - e.g., even when dealing with propositional Horn theories, or wh~n c?n­ sidering with only atomic queries, or when considenng only a bounded number of transformations, et?.I We then show that this task cannot even be approximated: i.e., that no efficient algorithm can find a theory whose inaccuracy is even close to (i.e., within a particular small polynomial of) optimum! We also prove that the~~ nega­ tive results apply even when we are only generahzmg, or only specializing, the initial theory. We also discus.s .the efficiency of other restricted variants of theory reviswn, providing sharp boundaries that describe exactly when this task is, versus is not, tractable. 1 Throughout, we will assume that PfNP [GJ79], which implies that any NP-hard problem is intractable. This also implies certain approximation claims, presented below. We view these results as sanctioning the standard ap­ proach of using a set of transformations to hill-climb to a local optimum, based on a set of samples: The labeled training samples are required to obtain the needed distri­ bution information, and the realization that no tractable algorithm will be able to find the global optimum justi­ fies hill-climbing to a local optimum, within the space formed using specified transformations. We close this section by describing related research. 2 Related Research: While most learning systems begin with an "empty theory" and attempt to learn a target function (perhaps a decision tree, or a logic program), theory revision processes work by modify­ ing a given initial theory. There are several imple­ mented theory revision systems. Most use essentially the same set of transformations we describe - e.g., AUDREY [WP93], FONTE [MB88], EITHER [0M94) and !:l [LDRG94) all consider adding or deleting antecedents or rules. Our analysis, and results, can easily be applied to many other types of modifications - e.g., specializ­ ing or ~eneralizing antecedents [OM94), using "n-of-m rules" lBM93], or merging rules and removing chains paths of rules that produced incorrect results [Coh90; Coh92]. 3 While these projects provide empirical evi­ dence of the effectiveness of their specific algorithms, and deal with classification (i.e., determining whether a given element is a member of some target class) rather than general derivation, our work formally addresses the com­ plexities inherent in finding the best theory, for handling arbitrary queries. Finally, note that, in some cases, our task can require extracting the best consistent sub-theory from a given inconsistent theory. From this perspective, our work is related to "Knowledge Representation" form of theory revision, ala Gardenfors [Gar88; AGM85], Katsuno and Mendelzon [KM91) and many others. Our work differs by using the notion of expected accuracy to dictate which of the "revisions" is best. ## 2 Framework We define a "theory" as a collection of (propositional or first order) Horn clauses, where each clause is a disjunc­ tion of literals, at most one of which is positive. Bor­ rowing from [Lev84; DP91], we also view a theory T as a function that maps each query to its proposed answer; hence, T: Q 1-+ A, where Q is a (possibly infinite) set of Horn queries, and A= { No, Yes } is the set of possible answers. 4 Hence, given T1(h) =Yes, T1(i) =No and T1(i e,j .) =Yes. Of course, different theories can return different answers to a given query: For example, let T2 be a theory that differs from T 1 only by excluding the "g :- e" rule; then T 2 (h) =No. 2 The technical report [Gre95b] provides a more extensive literature survey, as well as proofs of the theorems. 3 The companion paper [Gre95a] considers yet other ways of modifying a theory, viz., by rearranging its component rules or antecedents. ![Image](https://ijcai.org/proceedings/1995/fulltext/150/image_000000_4a672bec201fcff1d52b2749f95a5fe2e84dc3189aa0008ecaedcb9a13317902.png) While the non-atomic queries may seem unusual at first, they are actually quite common. For example, a medical expert system typically collects relevant data { f1 (p), ... , fn (p) } about an individual patient p, then determines whether p has some specific disease diseasei; i.e., if T U { f1 (p), ... , fn (p) } f= diseasei (p), where Tis the expert system's initial theory that contains gen­ eral information about diseases, etc. Notice this entail­ ment condition holds iff T f= -,f1 (p) V ... V -,fn (p) V diseasei (p); i.e., iff the Horn query "diseasei (p) :- f1 (p), ... , fn (p)" follows from the initial theory. (See also "entailment queries" [FP93).) We assume there is a single correct answer to each question, and represent it using the real-world oracle 0 : Q 1-+ A. Here, perhaps, 0( h) = No, meaning that "h" should not hold. We say an oracle is con­ sistent if it produces the same answers as a Horn the­ ory, over the set of queries Q. N.b., we will sometimes deal with inconsistent oracles; e.g., where 0( a) = Yes, O(b :- a)= Yes, and O(b) =No. Our goal is to find a theory that is as close to 0( · ) as possible. To quantify this, we first define the "accu­ racy function" a(·, ·) where a(T, q) is the accuracy of the answer the theory T returned for the query q: (Notice a(T, ·) implicitly depends on the oracle 0( · ).) Hence, as O(h) =No, a(T2 , "h") = 1 as T 2 provides the correct answer while a(T 1, "h") = 0 as T 1 returns the wrong answer. This a(T, ·) function measures T's accuracy for a sin­ gle query. In general, our theories must deal with a range of queries. We model this using a stationary, but unknown, probability function Pr : Q 1-+ [0, 1), where Pr(q) is the probability that the query q will be posed. Given this distribution, we can compute the "expected accuracy" of a theory, T: We will consider various sets of possible theories, T = {Ti}, where each such T contains the set of theories formed by applying various sequences of transformations to a given initial theory; see Section 2.1 below. Our chal­ lenge is to identify the theory T opt E T whose expected accuracy is optimal; i.e., 4 To simplify the presentation, the bulk of this paper will deal only with propositional logic; Section 2.3 below describes the extensions needed to deal with predicate calculus. There are two challenges to finding such optimal the­ ories. The first is based on the observation that the ex­ pected accuracy of a theory depends on the distribution of queries, which means different theories will be opti­ mal for different distributions. While this distribution is not known initially, it can be estimated by observing a set of samples (each a query/answer pair), drawn from that distribution. Section 2.2 below discusses the num­ ber of samples required to be confident of obtaining the information needed to identify a good T* E T, with high probability. We are then left with the challenge of computing the best theory, once given this distributional estimate. Sec­ tion 3 addresses the computational complexity of this process, showing that the task is not just intractable, 5 but it is also not approximatable - i.e., no efficient al­ gorithm can even find a theory whose expected accuracy is even close (in a sense defined below) to the optimal value. We first close this section by describing the transfor­ mations we will use to define the various spaces of the­ ories, then discussing the sample complexity of the im­ plied learning process and finally providing the exten­ sions needed to deal with predicate calculus. ## 2.1 Standard Transformations Standard theory revision algorithms implicitly explore the space of possible theories :E 00 [T0] = {o-(To) I O" E :E 00 }, which contains the theories formed by applying some sequence of theory-to-theory transformations a- E :E 00 to the given initial theory T 0 . Each O" = 1"1 o 1"2 o . . . o Tk E :E 00 sequence is formed from :E = :EDR U :EAR U :EDA U :EAA, where each 'TDR E :EDR deletes a rule from the theory, each r AR E :EAR adds a new rule to the theory, each 'TDA E :EDA deletes an existing antecedent from an existing rule, and each 'TAA E :EAA adds a new antecedent to an existing rule. In some situations, we will consider "K-bounded sequences" whose members O" = r1 o r2 o ... o Tk E :EK are sequences of transformations whose total cost c(o-) = c( r1) + c( r2 ) + ... + c( Tk) are at most K, where the cost c( r) of the transformation r is the number of symbols added to, or deleted from, T to form r(T). In the propositional case, c( rAA) = c( rDA) = 1 for each trans­ formation that either adds or deletes an antecedent; and c(r:R) = c(rf!R) = IPI for each add-rule (resp., delete­ rule) transformation that adds (resp., deletes) the rule p, which has 1 conclusion and JpJ-1 antecedent literals. 5 As a(T, q) requires computing T(q), which can require proving an arbitrary theorem, this computation alone can be computationally intractable, if not undecidable. Our results show that the task of finding the optimal theory is intractable even given a poly-time oracle for these arbitrary derivations. Of course, as we are considering only Horn theories, these computations are guaranteed to be poly-time in the proposi­ tional case [BCH90]. As an example, applying the 3-element sequence u = r:~e; +q o r{;!: 1 o rf~c,di -c with total cost c(o-) c(r:~e; +q) + c(rt!!:1) + c(rf~c,d; \_J 1 + 2 + 1 = 4, will transform T 1 into o-(T 1) = r:~e; +q( rt!!:f( rf~c,d; -c( T1))) which is a theory with 8 clauses that differs from T 1 by including the clause "g: -e, q" rather than "g: -e", including the clause "f : -d" rather than "f : -c, d", and by including an extra clause "b : -f". Finally, we will also consider various other restricted spaces of transformation-sequences, which ·are formed from specified types of transformations; e.g., ## 2.2 Sample Complexity We can use following standard Computational Learn­ ing Theory theorem to bound the number of samples required to obtain the information needed to identify a good T* E T with high probability; showing in partic­ ular how this depends on the space of theories T being considered: Theorem 1 (from [Vap82, Theorem 6.2]) Given a class of theories T and €, 8 > 0, letT. E T be the theory with the largest empirical accuracy after samples (each a labeled query), drawn from the station­ ary distribution, Pr( ·). Then, with probability at least 1-8, the expected accuracy ofT · will be within € of the optimal theory in T; i.e., Pr[ A( T ·) 2: A( T opt) - € J 2: 1 - 8, using the T opt from Equation 2. This means a polynomial number of samples is suffi­ cient to identify an €-good theory from T with probabil­ ity at least 1 - 8, whenever ln(JTI) is polynomial in the relevant parameters. Notice this is true for most of the classes of theories being considered; e.g., as :E-R(T) is the power-set of the rules in T, J:E-R(T)I = 21Rules(T)I, which means Jln(:E-R(T))I = JRules(T)I = O(JTI), which clearly is polynomial in the size of the initial the­ ory. This "ln(JTI) = poly(ITI)" claim is slightly prob­ lematic for transformations that can add symbols, no­ tably for :E+R and :E+A. But even here, the sample complexity remains polynomial in the size of the re­ vised theory, which effectively means again that sample­ efficient learning remains possible; cf., "nonuniform" pac-learning [BI88] ## 2.3 Dealing with Predicate Calculus To handle predicate calculus expressions, we have to con­ sider answers of the form {Yes[ {Xi/vi} ]}, where the expression within each Yes[·] is a binding list of the free variables, corresponding to a single answer to the query. For example, given the theory 6 the query short (Y) will return T pc (short (Y)) = {Yes[{Y/fred}] }, the query rich(Z) will return the pair of answers T pc(rich(Z)) = {Yes[{ Z/john }], Yes[{Z/fred}]}, and Tpc(eligible(A)) = {Yes[{ A/john}] }. As 0( ·)and T(·) each returns a set of answers to each query, we therefore define T 's accuracy score as a(T, a)= ~g~:~8H:ll E [0, 1] . All of the theorems in this paper hold even when considering only non-recursive Datalog (i.e., "function-free") theories. ## 3 Computational Complexity Our basic challenge is to produce a theory T opt whose accuracy is as large as possible. The previous section supplied the number of samples needed to guarantee, with high probability, that the expected accuracy of the theory whose empirical accuracy is largest, T., will be within f of the expected accuracy of this T opt . This sec­ tion discusses the computational challenge of determin­ ing this T. , given this distributional estimate. We show first that this task is tractable in degenerate trivial situ­ ations: when considering (1) only atomic queries posed to a (2) propositional theory and being allowed (3) an arbitrarily large number of modifications to the initial theory, to produce (4) a perfect theory (i.e., one that returns the correct answer to every query). This task becomes intractable, however, if we remove (essentially) any of these restrictions: e.g., if we seek optimal (rather than only seeking "perfect") propositional theories and are allowed to pose Horn queries, or if we consider predi­ cate calculus theories. It also remains intractable even if we restrict the number of modifications allowed, which implies that the task of determining the smallest num­ ber of modifications required to find a perfect theory is intractable. We next show that these tasks are not just intractable but worse, they are not even approximatable, except in the most trivial of situations. We also consider two special subtasks by restricting the allowed types of transformations, to consider revision processes that only specialize (respectively, only gener­ alize) the initial theory. We show that these tasks, also, are intractable and non-approximatable in essentially all situations; i.e., except when all four of the above con­ ditions hold. 7 Figures 1 and 2 summarize the various cases. 6 Following PROLOG'S conventions, we will capitalize each variable, as in the · "X" above. 7 Actually, there is one other tractable case in the gener­ alization situation; see Figure 1. ## 3.1 Basic Complexity Results To formally state the problem: Definition 1 (TR[:Et] Decision Problem) INSTANCE: - Initial theory T; - Labeled training sample S = { (qi, 0( qi )) } con­ taining a set of Horn queries and the correct answers; and - Probability value p E [0, 1] . The :Et [·] function maps a theory to a set of candidate revised theories; here, we will consider various I;±R,±A transformation sets. To simplify our notation, we will write A( T ) for As( T ). We will also consider the following special cases: TRPert[:Et] requires that p = 1 (i.e., seeking perfect theories, rather than "optimal" theories TR(opt) [:Et]); TRProp[:Et] deals with propositional logic (rather than predicate calculus, TR(PredCal) [:Et]); and TRAtom[:Et] deals with only atomic queries (as opposed to Horn queries, TR(Horn) [:Et]). We will also use TRDisj [:Et] to refer to the task when the queries can be arbitrary disjunctions, which need not be Horn. (While the other subscripts are restrictions on TR[:EtJ, this Disj case is more permissive.) We will also combine subscripts, with the obvious meanings. When TRx [:Et] is a special case of TR,p [:EtJ, finding that TRx [:Et] is hard imme­ diately implies that TR,p [:Et] is hard. Similarly, seeing that TR,p[:Et] is easy immediately implies that each spe­ cial case of TR,p [:Et] is easy. As a final note: all of the hardness results presented in this paper hold even if we only consider "3-CNF Horn theories" - i.e., rules whose antecedents contain at most 2 literals. Here, it is easy to find the optimal theory in cer­ tain degenerate cases, where either the individual queries can be decoupled (e.g., when using atomic propositional queries) or when our actions are forced (e.g., when seek­ ing perfect propositional theories): just throw away the original theory, then add in propositions corresponding to the "Yes-labeled queries". In every other case, how­ ever, the task is intractable: Theorem 2 The TRProp,Atom ,(Opt)[:E 00 ] and TRProp,(Horn),Pert[:E 00 ] decision problems are easy; each other problem is NP-hard. (This information is summarized in lower left "Un­ bounded, Arbitrary" graph of Figure 1.) The above theorem describes the complexity of com­ puting the best theory when we are allowed to use an arbitrarily expensive sequence of transformations. We get an even stronger negative results if we restrict the "expense" of the transformation sequence: ## Theorem 3 For some K E z+' the TRProp ,Atom,Pert[:EK] decision problem is NP-hard. This is true even if we consider only labeled queries produced by a consistent oracle (i.e., Any task that "projects" down to an NP-hard task, along any axis, is NP-hard. Here, this means all of the "cross terms" are NP-hard. (For example ThRevPredCal,Horn,Perf[E 00 ) is NP-hard, as its projection to the "Prop-PredCal X Perf-Opt" plane, ThRevPredCal,Atom,Perf[E 00 ) is NP-hard.) The ThReVProp,Horn ,Opt[E 00 ] case is shown explicitly as each of its projections is easy; the figures omit all other cross-terms. ![Image](https://ijcai.org/proceedings/1995/fulltext/150/image_000001_b75b224b04c9f3a2d3cf4fe7d568b524cf604814eddc4a950ab4ec1f9b0e0153.png) Figure 1: Tractability of Theory Revision Tasks even when there is a Horn theory that correctly labels all of the queries). The observation that determining such "K-step perfect theories" is NP-hard leads immediately to: Corollary 3.1 It is NP-hard to compute the minimal­ cost transformation sequence required to produce a per­ fect theory (i.e., to compute the smallest K for which there is aT perfect E :EK[T] such that A( T perfect) = 1}, even in the propositional case when considering only atomic queries. It is also NP-hard to compute the "minimal-length" transformation, where the length of the transformation sequence r 1 o r 2 o ... o 1"k is simply k - i.e., when each transformation has "unit cost". This negative result shows the intractability of the ob­ vious proposal of using a breath-first transversal of the space of all possible theory revisions: First test the ini­ tial theory T0 against the labeled queries, and return T0 if it is 100% correct. If not, then consider all theories formed by applying a single (unit-cost) transformation, and return any perfect T 1 E :E 1 [T0]; and if not, consider all theories in :E 2 [T0] (formed by applying sequences of transformations with cost at most two), and return any perfect T2 E :E 2 [T0]; and so forth. ## 3.2 Approximatability Many decision problems correspond immediately to opti­ mization problems; for example, the MrNGRAPHCOLOR decision problem (given a graph G = (N, E) and a pos­ itive integer K, can each node be labeled by one of K colors in such a way that no edge connects two nodes of the same color; see [GJ79, p191(Chromatic Number)]) corresponds to the obvious minimization problem: Find the minimal coloring of the given graph G. We can sim­ ilarly view the TRx [:Et] decision problem as either the maximization problem: "Find the T' E :r;t [T] whose ac­ curacy is maximal" or the minimization problem: "Find the T' E :r;t [T] whose inaccuracy is minimal", where a theory's inaccuracy is obviously INA( T) = 1 - A( T ). (While the maximally accurate theory is also mlmmally inaccurate, these two formulations can lead to different approximatability results.) For notation, let "MAXTRx[:Et]" (resp., "MrNTRx[:Et]") refer to the maximization (resp., minimization) problem. Now consider any algorithm B that, given any MrNTRx [:Et] instance x = (T, S) with initial theory T and labeled training sample S, computes a syntactically legal, but not necessarily optimal, revision B(x) E :r:t[T] . Then B's "performance ratio for the instance x" is de­ fined as where opt(x) = optMinTRx(:~::l)(x) is the optimal solution for this instance; i.e., opt( x) is the theory Topt E :r;t [T] with minimal inaccuracy over S. We say a function g( ·) "bounds B's performance ratio (over MrNTRx [:Et])" iff where lxl is the size ofthe instance x = (T, S ), which we define to be the number of symbols in T plus the number of symbols used in S. Intuitively, this g(·) function in­ dicates how closely the B algorithm comes to returning the best answer for x , over all MINTRx[:Etj instances x. Now let Poly( MINTRx[:Etj) be the collection of all polytime algorithms that return legal answers to MrNTRx[:Etj instances. It is natural to ask for the algo­ rithm in Poly( MrNTRx [:Et] ) with the best performance ratio; this would indicate how close we can come to the optimal solution, using only a feasible computational time. For example, if this function was the constant 1 for MrNTRProp[:E 00 ], then a poly-time algorithm could produce the optimal solution to any MINTRProp[:E 00 ] instance; as TRProp[:E 00 ] is NP-complete, 8 this would Unbounded mean P = N P, which is why we do not expect to ob­ tain this result . Or if this bound was some constant c(x) = c E !R, then we could efficiently obtain a solu­ tion within a factor of c of optimal, which may be good enough for some applications. 9 8 While Theorem 2 only proves TRProp(E 00 ) to be NP- (· = NoTPOLYAPPROX; 0 =Easy (as poly-time decision) ; ? =unknown approximatability class) ![Image](https://ijcai.org/proceedings/1995/fulltext/150/image_000002_29ed720a7a0c29ca9c2820a1bd8e2816da7c2c8911ef0b5df79b590f2f18bc12.png) ![Image](https://ijcai.org/proceedings/1995/fulltext/150/image_000003_d5c1e66312a1060d59992265821dbd4576c8a3e34f3cbb6b917535e92bf52b06.png) ![Image](https://ijcai.org/proceedings/1995/fulltext/150/image_000004_9fdc62618a6643604da4822ef1e56dd982c975fb4ce4e1dcfde85abfe7f6c3e5.png) Figure 2: Approximatability of Theory Revision Tasks However, not all problems can be so approximated. Following [CP91; Kan92], we define Definition 2 A minimization problem MINP is NOT­ POLY APPROX if there is a "( E !R+ such that Lund and Yannakakis [LY93] prove that the "MIN­ GRAPHCOLOR minimization problem" is NoTPOLYAP­ PROX. We can use that result to prove: While these results may at first seem trivial, given that it is NP-hard to determine if a perfect theory exists, no­ tice from Equation 3 that MinPer.ftMINTR[~""]]( ·) es­ sentially ignores such perfect theories. Note also that this result holds in the context based on an "inconsis­ tent" oracle; in such situations, no theory can be perfect. As lxl can get arbitrary large, this result means that these MrNTR" [L:t] tasks cannot be approximated by any constant, nor even by any logarithmic factor nor any sufficiently small polynomial, etc. ## 3.3 Special Cases If the theory is too general (i.e., returns Yes too often), then we may want to consider "specializing" it by apply­ ing only the "delete rule" and "add antecedent" transfor­ mations. In particular, recall that L;+A,-R[T] is the set of theories obtained usinR an arbitrary number of such transformations, and L;- [T] (resp., L;+A[T]), is the set of theories obtained by applying an arbitrary number of "delete rule" (respectively, "add antecedent") trans­ formations. Similarly, if the theory is too specific (i.e., hard, this problem is clearly in NP. 9 There are such constants for some other NP-hard min­ imization problems. For example, there is a polynomial­ time algorithm that computes a solution whose cost is within a factor of 1.5 for any TRAVELINGSALESMAN-WITH­ TRIANGLE-EQUALITY problem; see (GJ79, Theorem 6.5). returns No too often), then we may want to consider "generalizing" it by applying only the "add rule" and "delete antecedent" transformations; here, we consider L;+R,-A[T], L;+R[T] and L;-A[T], which are the set of theories obtained by applying an arbitrary number of such transformations. Even using only these transformations, almost all of these tasks remain intractable: Theorem 5 It is easy to solve TRProp,Perf[Q] for Q E {L;+R,-A, L;+R,L;-A}, TRProp,Atom,Per f [S] for S E {L;-R,+A, L;-R, L;+A}. However, every other situation, formed by any other combination of restrictions {read "subscripts") is NP­ hard. {See middle and right of Figure 1.) Worse, Theorem 6 Unless P = NP, each of the following is N OTPOLY APPROX: - MINTR(PredCal},Atom[S], MINTRProp,(Horn}[S] for S E {L;-R,+A' L;-R' L;+A } - MINTR(PredCal},Atom [Q], MINTRProp ,Disj [Q] for Q E {L:+R,-A' L;+R' L;-A } . {See middle and right of Figure 2.) In each of these cases, however, there is a trivial polynomial-time algorithm that can produce a theory whose accuracy (n.b., not inaccuracy) is within a factor of 2 of optimal. That is, using the ratio of an algorithm's accuracy to the optimal value, The companion paper [Gre95a] considers other related cases, including the above special cases in the context where our underlying theories can use the not ( ·) opera­ tor to return Yes if the specified goal cannot be proven; i.e. , using Negation-as-Failure [Cla78]. It also considers the effect of re-ordering the rules and the antecedents, in the context where such shuffiings can affect the answers returned. In most of these cases, we show that the cor­ responding maximization problem is not approximatable within a particular polynomial. (The extended [Gre95b] explains the asymmetry be­ tween TRProp,PerJ[E-R] versus TRProp,PerJ[E+R], and discusses how these results relate to both inductive logic programming, and to default theories.) ## 4 Conclusion A knowledge-based system can produce incorrect an­ swers to queries if its underlying theory is faulty. A "theory revision" system attempts to transform a given theory into a related one that is as accurate as possi­ ble, using a given set of correctly-answered "training queries". This report describes both the sample and computational complexity of this task. It first provides the number of samples required to obtain the statistics needed to identify a theory (from within a class of the­ ories defined by applying various standard transforma­ tions to a given initial theory) whose accuracy will be within € of the optimal theory in this class, with prob­ ability at least 1 - 6. It then shows that, in general, the task of computing this globally optimal theory is intractable - and worse, that no polynomial time algo­ rithm can be guaranteed to find a solution that is even close to optimal (given the standard P :f; N P assump­ tion). We also present special cases of these tasks, which pin-point exactly when the task becomes tractable. ## References 1. Carlos E. Alchourr6n, Peter Giirdenfors, and David Makinson. On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic Logic, 50:51Q-30, 1985. 2. E. Boros, Y. Crama, and P.L. Hammer. Polynomial-time inference of all valid implications for horn and related formulae. Annals of Mathe- matics and Artificial Intelligence, 1:21-32, 1990. 3. G. Benedek and A. ltai. Nonuniform learnability. In Proceedings ICALP-88, pages 82-92, 1988. 4. Paul T. Baffes and Raymond J. Mooney. Sym- bolic revision of theories with M-of-N rules. In Proceedings of IJCAI-99, August 1993. 5. K. Clark. Negation as failure. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 293-322. Plenum Press, New York, 1978. 6. William W. Cohen. Learning from textbook knowledge: A case study. In Proceeding of AAAI- 90, 1990. 7. William W. Cohen. Abductive explanation-based learning: A solution to the multiple inconsis- tent explanation problems. Machine Learning, 8(2):167-219, March 1992. 8. P. Crescenzi and A. Panconesi. Completeness in approximation classes. Information and Compu- tation, 93(2):241-62, 1991. 9. Susan Craw and Derek Sleeman. Automating the refinement of knowledge-based systems. In L.C. Aiello, editor, Proceedings of ECAI 90. Pitman, 1990. 10. Jon Doyle and Ramesh Patil. Two theses of knowledge representation: Language restrictions, LEARNING taxonomic classification, and the utility of repre- sentation services. Artificial Intelligence, 48(3) , 1991. 11. Michael Frazier and Leonard Pitt. Learning from entailment: An application to propositional horn sentences. In Proceedings of IML-93, pages 120- 27. 12. Morgan Kaufmann, 1993. 13. Peter Gardenfors. Knowledge in Flux: Modeling the Dynamics of the Epistemic States. Bradford Book, MIT Press, Cambridge, MA, 1988. 14. Michael R . Garey and David S. Johnson. Com- puters and Intractability: A Guide to the Theory of NP-Completeness. W . H. Freeman and Com- pany, New York, 1979. 15. Russell Greiner. The challenge of revising impure theories. In Proceedings of the Twelfth Int erna- tional Machine Learning Conference, 1995. 16. Russell Greiner. The complexity of the- ory revision. Technical Report SCR-95- TR-539, Siemens Corporate Research , 1995. ftp://scr.siemens.com/pub/learning/Papers/ greiner/comp-tr.ps. 17. Viggo Kann. On the Approximability of NP- Complete Optimization Problems. PhD thesis, Royal Institute of Technology, Stockholm, 1992. 18. Hirofumi Katsuno and Alberto Mendelzon. On the difference between updating a knowledge base and revising it. In Proceedings of KR-91, pages 387-94, Boston, April 1991. 19. Pat Langley, George Drastal, R. Bharat Rao, and Russell Greiner. Theory revision in fault hierar- chies. In Proceedings of The Fifth International Workshop on Principles of Diagnosis {DX-94 ), New Paltz, NY, 1994. 20. Hector J. Levesque. Foundations of a functional approach to knowledge representation . Artifi cial Intelligence, 23:155-212, 1984. 21. Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization prob- lems. In Proceeding of Twenty-fifth Annual A CM Symposium on Theory of Computation {STOC- [MB88] [OM94] [Pol85] [Vap82] [WP93] 99}, pages 286-93, 1993. 22. S. Muggleton and W . Buntine. Machine invention of first order predicates by inverting resolution. In Proceedings of IML-88, pages 339-51. 23. Morgan Kaufmann, 1988. 24. Dirk Ourston and Raymond J. Mooney. The- ory refinement combining analytical and empir- ical methods. Artificial Intelligence, 66(2) :273- 310, 1994. 25. P.G. Politakis. Empirical Analysis for Expert Sys- tems. Pitman Research Notes in Artificial Intelli- gence, 1985. 26. V.N. Vapnik. Estimation of Dependences Based on Empirical Data. Springer-Verlag, New York, 1982. 27. James Wogulis and Michael J . Pazzani. A methodology for evaluating theory revision sys- tems: Results with Audrey II. In Proceedings of IJCAI-93, pages 1128-1134, 1993.