The Comparative Linguistics of Knowledge Representation

1 Introduction

Many important knowledge representation formalisms have been proposed, used, and studied during the past fifteen years, including various forms of propositional logic, nonmonotonic formalisms, decision trees, and so on. There is now a host of methods available for rep­ resenting complex knowledge, and for reasoning about it. An interesting question thus arises: How is one to evaluate and compare different knowledge represen­ tation formalisms? Besides the practical aspect of this question with respect to choosing the "best" formalism for a given application, environment, and resource con­ straints, a methodology for comparing and evaluating knowledge representation methods may lead to useful in­ trospection, new insights, and to the discovery of better approaches.

In this regard, one must consider several aspects of the desirability and effectiveness of a knowledge representa­ tion formalism:

· A part of the work was done while the author was em­ ployed at AT&T Bell Laboratories, Murray Hill. Research supported by an NSF grant.

tResearch supported by an NSF grant.

Henry Kautz

AI Principles Research Department

AT&T Bell Laboratories Murray Hill, NJ 07974, USA

email: kautz@research.att.com

Bart Selman

AI Principles Research Department AT&T Bell Laboratories

Murray Hill, NJ 07974, USA

email: selman@research.att.com

1. Does it support efficient reasoning? The most com­ mon use of a knowledge base is for deciding whether a statement can be inferred from the available knowl­ edge, and hence this question is of central importance. Much research effort has been invested in recent years to clarifying this issue, and this aspect of knowledge repre­ sentation is by now very well understood. In brief, all knowledge representation formalisms can be subdivided into three categories with respect to the complexity of their inference problem.
2. Classical propositional logic, perhaps the most basic knowledge representation formalism, has an NP­ complete inference problem [Cook, 1971].
3. More sophisticated and non-monotonic for­ malisms, such as circumscription, default logic, non­ monotonic logic, autoepistemic logic, etc., have infer­ ence problems that are even harder: complete for the second level of the polynomial hierarchy, see [Cadoli and Lenzerini, 1994; Eiter and Gottlob, 1993; Gottlob, 1992]; model preference default theories [Selman and Kautz, 1990] have even higher complexity [Papadim­ itriou, 1991].
4. Finally, weaker versions of the above formalisms provide polynomial-time inference at the expense of our next criterion, expressibility. These include Horn clauses [Dowling and Gallier, 1984], Horn model preference de­ faults [Selman and Kautz, 1990], restricted forms of de­ fault logic [Kautz and Selman, 1992], etc.
5. An orthogonal criterion for the desirability and usefulness of a knowledge representation method is, how expressive is it? First we must formalize what we mean by "expressive." The most natural notion of expressive­ ness is provided by model theory: Since the propositional case of each of these formalisms has semantics in terms of models or truth assignments, any knowledge base can be thought of as representing a set of truth assignments, that is, of "possible worlds." This suggests a notion of equivalence: Two knowledge bases, possibly in different formalisms, are equivalent if they encode the same set

of possible worlds. Thus, here is a first try at a frame­ work for comparing formalisms in terms of expressibility: Consider formalism A at least as expressive as formal­ ism B if and only if any knowledge base in B has an equivalent knowledge base in A.

There are serious drawbacks to this proposal. First, all diverse formalisms in 1a and 1b above are trivially equally expressive, since any set of models can in princi­ ple be expressed by each of them. For example, proposi­ tional logic is exactly as expressive as the more sophisti­ cated default logics, even the (soon to be proved) much more powerful preference defaults. Only the formalisms in (1c) above are provably inferior; however, this is the result of a conscious sacrifice of expressibility in the in­ terest of efficiency. As we shall point out in Section 4, where we compare sublanguages of propositional logic, it is more meaningful to compare knowledge representa­ tion formalisms in terms of their relative performance at sets of models that they can both express .

1. A much more interesting, but also more subtle, question one can ask about a knowledge representation formalism is this: How succinctly can the formalism ex­ press the sets of models that it can? We think that this is the more interesting expressibility criterion; it is the main methodological contribution of this paper. That is, we consider formalism A to be stronger than formal­ ism B if and only if any knowledge base in B has an equivalent knowledge base in A that is only polynomially longer, while there is a knowledge base in A that can be translated to B only with an exponential blowup. Using this criterion, we show that the known knowledge rep­ resentation formalisms form a hierarchy (Fig. 1) which is rather surprising in its strictness, as well as in the outcomes of the particular comparisons.
2. ( 4) We should mention here that another important question is, how does the knowledge representation for­ malism fare in the face of change? Change is impor­ tant in knowledge representation (for example, non­ monotonicity is a dynamic property). There are many formalisms in the literature for knowledge base updates and revisions; as was pointed out in [Eiter and Gott­ lob, 1992; Gogic et a/., 1994], none of the known for­ malisms supports efficient changes. [Gogic et a/. , 1994] propose a tractable revision mechanism using the theory approximation technique of [Selman and Kautz, 1991; Selman and Kautz, 1996]. Incidentally, change has its own expressiveness aspect (which changes in the set of models can be expressed, and how succinctly?), which is not at all understood at present .

In this paper we find that the representational suc­ cinctness criterion (3) above can tell us interesting and unexpected things about familiar knowledge represen­ tation formalisms . There is a tempting argument pur­ porting to prove that our criterion of representational succinctness (criterion 3) is just a disguise of computa­ tional complexity of inference (criterion 1 above) . The argument would be this:

If reasoning in formalism A is computation­ ally harder then reasoning in formalism B (i .e., there is a polynomial-time reduction from the satisfiability problem in the latter to the for­ mer) then any sentence from A can be trans­ lated (with polynomial blow up) to an equivalent sentence in B .

This argument is wrong. The difference between reductions and representational simulations between knowledge bases is subtle but important. A reduction must be computationally efficient , and must preserve the answer to the satisfiability problem (the emptyness/non­ emptyness aspect of the corresponding set of mod­ els), whereas representational simulations must main­ tain the precise set of models, and need not be com­ putationally efficient (the simulating knowledge base need not be efficiently computable, as long as it ex­ ists) . This difference manifests itself in many compar­ isons. For example, one of our main results is that default logic is strictly more succinct than circumscrip­ tion, despite the fact that their inference problems are known to be computationally equivalent [Gottlob, 1992; Eiter and Gottlob, 1993]. For another example, char­ acteristic models (whose satisfiability problem is trivial) can be sometimes more succinct than CNF (whose sat­ isfiability problem is, of course, NP-complete) . Finally, we know how to translate default theories to model pref­ erence defaults only in a nonconstructive way (Proposi­ tion 2). Evidently, the complexity arguments involved in such comparisons have to be much more subtle than the crude one outlined above. (However, a more sophis­ ticated version of this "translation via complexity" ar­ gument is used in Proposition 2.)

We next highlight our results on the representational succinctness criterion (see Fig. 1 for a full depiction of our results).

1. Circumscription and default logic are more pow­ erful with respect to representational succinctness then propositional logic (this had been observed for the case of circumscription by [Cadoli et a/. , 1994; Cadoli et a/. , 1995]). This result provides a "silver lining" for the high intractability of circumscription and default logic: In these formalisms one may need exponentially more suc­ cinct expressions, and thus increased intractability is not necessarily a real threat .
2. Default logic can be exponentially more succinct than circumscription. This is a rather surprising result in view of the computational equivalence of the two for­ malisms, and it is perhaps quite revealing of the relative power and desirability of these formalisms (heretofore in­ distinguishable in terms of their inference complexity). Also, model preference defaults can be exponentially more succinct than default logic, or any other formal­ ism whose inference problem can be done in polynomial space; this is rather unexpected, since model preference defaults had been considered as a rather crude and un­ sophisticated knowledge representation formalism.
3. Lower in the hierarchy, CNF and DNF have no advantage over Horn formulas and characteristic models, when a Horn set is to be represented (recall that we are comparing knowledge representation formalisms at the intersection of their expressibility domain); this suggests that we should choose a Horn formula representation

whenever at all possible. Similarly, every Horn set has a set of characteristic models of size no larger than the one that of the best DNF representation. What is more surprising, the reverse statement does not hold, i.e. there are some functions having a short characteristic models representation but no short DNF representation. On the other hand, Horn formulas and characteristic model representations are mutually orthogonal, in that they can take exponential advantage of each other.

Some of our comparison results are not proven to hold, but are shown to be "very likely," as their refutation would disprove certain widely accepted conjectures in complexity theory. The scientific community has been trying to resolve a number of class containments prob­ lems for years (the question of whether P=NP is the best known, but certainly not the only, important question in complexity theory alluded to here), and although the fi­ nal answer to each of these questions continues to be elusive, a certain amount of intuition toward the correct answer has been obtained. For example, we think that P#NP because, roughly speaking, if there were a polyno­ mial algorithm for satisfiability or for the traveling sales­ man problem, we would probably have found it. 1 Sim­ ilarly, we believe that NP#co-NP, because we have not found a polynomially succinct variant of resolution that works (or a characterization of non-Hamiltonian graphs, say) .

But what about the following problem: Given a propo­ sitional formula ¢ and a subset E of the set of all its variables, is it possible to fix the variables in E so that ¢ becomes a tautology? Not only there is no known poly­ nomial algorithm for this problem, but there is strong evidence that it does not even belong to NP or in co-NP. The class for which the problem is complete is called E2, and is at the second level of the polynomial hierarchy. The polynomial hierarchy is extended in this way to E3, E4 , and so on; their complementary classes are denoted by II2 , II3 , etc. Finally, the class of all problems solvable in polynomial space is even broader , as it contains all of the polynomial hierarchy (and probably much more). Exactly as we strongly believe that P#NP, although we have no proof, we also strongly believe that all these levels of the polynomial hierarchy, as well as polynomial space, are distinct. That is, it is considered very unlikely that the polynomial hierarchy collapses at any level (the lower the level, the stronger our confidence that collapse does not occur there) .

Therefore, once we show that a positive answer to a problem would imply that the polynomial hierarchy collapses, we can say that the answer to our problem is very likely to be negative. One well-known instance of this line of reasoning involves non-uniform complex­ ity classes. Let P /poly be the set of all problems that can be solved in polynomial time by Turing machines that take, together with their input x , say of length n , an advice string a(n) , depending only on n and not on x , and of length polynomial in n. Similarly for NP /poly. Although these classes now contain unsolv­ able problems, it is known that they "very likely" do not extend far beyond the corresponding classes in the hier­ archy. That is, it was shown in [Karp and Lipton, 1980; Yap, 1983] that, if NP is contained in P /poly, or even in co-NP /poly, then the polynomial hierarchy collapses. For more details about this and some other complexity issues mentioned in this paper see [Papadimitriou, 1993].

1 Notice the nonmonotonic reasoning going on here; in fact, deriving results based on assumptions such as "the polyno­ mial hierarchy does not collapse" is a fine example of non­ monotonic and counterfactual reasoning, or, equivalently, of building an extension supported by given defaults.

Arrows go from weaker to stronger formalisms. Two­ way arrows denote representational equivalence. In ar­ rows marked with a * the lower bound (A+B) depends on the non-collapse of the polynomial hierarchy. In the uppermost arrow, our proof that DL ""M P requires the introduction of new variables.

(

2 Definitions

In this section we introduce several well-known knowl­ edge representation formalisms, the notion of the size of a knowledge base or expression in this formalism, and what it means for a bit vector to be a model of a knowl­ edge base in the formalism.

P L is the class of all formulas in propositional logic. An assignment to the variables is model of a given propo­ sitional formula if it satisfies it. The size of a formula is the total number of connectives in it.

Let CC be the class of all circumscribed propositional formulas [McCarthy, 1980]. Vector a is a model of a formula F circumscribed over variables with indices from set M if a is a model of F, and no other model of F is contained in a with respect to M. The set of all such models is denoted as CIRCM(F), and when M contains all indices it is omitted and we write CIRC(F). The size of a circumscribed propositional formula is that of the uncircumscribed formula.

DL is the class of all pairs (D, W) where D is a set of defaults [Reiter, 1980) and W is set of propositional formulas. We say that a is a model of (D, W) iff there is an extension of ( D, W) satisfied by a (this is some­ times called sceptical reasoning). The size of a default theory is the total number of defaults in D, plus the to­ tal number of connectives appearing in W. Similarly for AEL, autoepistemic logic (this formalism is not treated extensively here).

M Pis the class of all sets of model-preference defaults [Selman and Kautz, 1990). A model preference default is an object of the form (A -+ b), where A is a set of literals and b is a literal. If Dis a set of model-preference defaults, D induces a directed graph G D on {0, 1 }n as follows : If a,/3 E {0, l}n, then (a,/3) E GD (we say that a is preferred to f3 with respect to D) if there is a default (A-+ b) in D such that (a) a and f3 are identical with respect to all variables outside b; (b) both a and f3 satisfy all literals in A; and (c) f3 satisfies band a does not. Finally, we say that a is a model of D if whenever there is a path in G D from a to some other bit vector /3, then there is a path from f3 back to a. The size of a set of defaults is the total number of literals in all of its defaults.

We also examine certain important special cases of propositional logic. By DN F we denote the class of all formulas in disjunctive normal form. A formula is in disjunctive normal form if it is a disjunction of conjuncts, where conjunct is a conjunction of literals. The size of a DNF formula is the total number of connectives. A bit vector is model of given DNF formula if it satisfies at least one disjunct. Similarly, C N F is the class of all formulas in conjunctive normal form. The size is again the total number of connectives, and a vector is model of given CNF formula if it satisfies all conjuncts.

By H we denote the class of all formulas in conjunc­ tive normal form such that each clause has at most one unnegated literal. The formalism is very popular be­ cause there is a fast al~orithm for satisfiability checking of Horn formulas (see lDowling and Gallier, 1984)) and because of its connection to logic programming. Un­ fortunately, not every set can be represented by Horn formulas.

C M denotes the class of all sets generated by a set of characteristic models. The idea originated in [Kautz et a/., 1993) . Since every Horn set is closed under bit­ wise multiplication, it makes sense to try to represent a Horn set not as the set of all its models but as the set of its "characteristic models," so that the original set is obtained as the closure of the set of characteristic mod­ els under bitwise multiplication. 2 For a set of vectors M we define closure(M) as the set of all vectors representable as bitwise product of some vectors from M. The set of models of a set of characteristic vectors M is precisely closure(M). In [Kautz et a/., 1993) it has been proved that H and CM are orthogonal, i.e. there are situations when one is better than the other for com­ pact knowledge representation. However, in Section 4 we give an intriguing method for simulating CM by H. It is also proved in [Kautz et a/., 1993) that abduction in CM can be done in polynomial time (the same problem is NP-complete for Horn formulas). The size of a set of characteristic models M ~ {0, l}n is IMI · n.

2The idea is later generalized in [Khardon and Roth, 1994] to capture non-Horn sets, and was successfully applied to model-based reasoning.

DT is the class of functions represented by decision trees. A decision tree is a binary tree such that each internal node has two edges emanating out of it -one labeled x;, the other labeled x;. Each leaf is labeled 0 or 1. A decision tree computes a Boolean function f( a), where a= (a1 , . .. , an), as follows: we start at the root of the tree and repeatedly follow the edge that evaluates to 1 (i.e. if a; = 0 then we chose edge labeled a;, if a; = 1 we chose the edge labeled a;) . We repeat the step until we arrive at a leaf, and the label of the leaf tells us the value that function at a . An assignment is a model of a given decision tree if it evaluates to 1. Notice that for every a there is exactly one path that can be traversed starting from the root. The size of a decision tree is the number of nodes in it.

Finally, let AC 3 be the class of all disjunctions of CNF and conjunctions of DNF. In other words, this is the class of all depth-3 unbounded fan-in circuits with OR and AND gates, and literals as leaves. The size of an AC 3 circuit is its number of gates. This is an interesting generalization of both C N F and D N F .

Let A and B be any knowledge representation for­ malisms such as the ones defined above. We say that A is at least as representationally succinct as B , written B""A if the following is true: For each knowledge base ¢JB in B there is a knowledge base ¢JAin A such that (a) ¢JA and ¢JB are defined over the same variables and have the same set of models, and (b) the size of ¢J A is polyno­ mially bounded in the size of ¢JB· Notice that we have no provision that ¢JA should be efficiently computable, give ¢JB· Also, A+B means that there is a knowledge base in A that has no equivalent polynomial knowledge base in B. We say that A is representationally strictly more succinct than B if B""A and A+B (these are the arrows in Fig. 1). We say that A and B are represen­ tationally equivalent if A""B and B"-'A. We say that A and B are representationally incomparable if A+ B and B+A. Since H and CM are not complete formalisms , in that they cannot represent all sets of models but only Horn sets, comparison with other formalisms will be re­ stricted to Horn sets. That is, we compare incomplete formalisms only at the intersection of the sets of models that they can express.

3 The Representational Succinctness Hierarchy

In this section we show that the formalisms defined above are related in terms of representational succinctness as shown in Fig. 1.

1. CC -f>P L unless NP~ P /poly (which would imply that the polynomial hierarchy collapses).

Lemma 1 For every n there is a propositional formula Tn of size polynomial in n such that to every 3CNF propositional formula F over n variables can be assigned a vector mF (in polynomial time) such that F is unsat­ isfiable iffmF is in CIRC(Tn)·

• Proof: The variables that Tn will contain are: c;, c~ where 1 :S i :S 8( ~ ) (i .e. , one c; and c~ for each possible 3-variable clause C;), XI, xz , . . . , Xn (one variable for each variable from F) and y (an ex­ tra variable). We define the set of clauses H as H =HI U Hz U H3 where:

HI {( c; VyV ap V aq V ar) : for every C; = ( ap V aq V ar)} Hz = {( c; V ci) : for 1 :S i :S 8( ~ )} , and H 3 = {(y--+ a;) : for 1 :S i :S n}

Our formula Tn will be the conjunction of clauses in H. For given F we chose mF to have c; set to 1 iff C; appears in F, ci being the opposite of c;, and Y = ai = ... = an = 1.

Claim 1 F is satisfiable iff mF is NOT a minimal model ofT.

• Proof: ( =>) If F has a satisfying assignment a then we built an assignment m' of Tn by ex­ tending a with y = 0 and setting each c; and ci like in mF.
• (i) Each clause C from HI is satisfied because either
• c; set to 0 or
• c; = 1 which implies that C; is in F and knowing that C; ~ C we have that C is satisfied.
• (ii) Each clause in Hz is satisfied by mF so it is satisfied by m'
• (iii) Each clause in H3 is satisfied because y = 0

We have now that m' is a model of Tn and it is less than mF which means that mF is not in CIRC(Tn)·

( <=) Suppose now that Tn has a model m' less than mF. It is easy to see that ffiF and m' must coincide on each c; and c;. Notice that m' must have y = 0 (otherwise H3 forces mF = m') and after plugging all c; , ci and y from m' into Tn we will be left with some clauses yet to be satisfied. Those are exactly the clauses from F and they can be satisfied only with a proper choice of a I, . . . , an which means that F is satisfiable. ·

This proves the lemma. · Suppose now that for any formula T there is a polysize formula T' such that CIRC(T) = T', i.e., the set of models for T' is the set of minimal models for T. From Lemma 1 we can then conclude that any prob­ lem from co-NPhas a poly-size circuit in the following way: reduce given instance of co-NPproblem to the ques­ tion of whether a formula F is a tautology (which is a co-NPcomplete problem,) find mF and Tn from the lemma, take then T' and check whether mF satisfies T' (which can be done in polynomial time). Therefore, our supposition would then imply co-NP~ P /poly, which implies that NP~ P /poly because P /poly is closed un­ der the complement. This theorem was proven indepen­ dently in [Cadoli et al., 1995] . The above proof builds on a construction introduced in [Kautz and Selman, 1992], and our result strengthens an earlier result in [Cadoli et al. , 1994]. 3

• Proof: Let us take a propositional formula T with vari­ ables {PI, pz, ... , Pn}. We define default logic .6. = ( D, W), with W = T and D = { d; = ~ : 1 :S i :S n}. Suppose now that m ECIRC(T). Then there is an extension obtained by applying those d; 's for which the i-th bit of m is 0, and that extension has only one model, m. No more defaults can fire be­ cause m would not be the minimal model. The other direction follows the same line: if S is an extension of .6. then it has only one model (the one that has bit i set to 0 only if d; has fired), and that model is minimal in T. This reduction belongs to the folklore of NMR community. . ·

3. DL -f>CC unless NP ~ co-NP /poly (which would imply that the polynomial hierarchy collapses).

Proof sketch: Because of space limitations, we can only provide an outline of the proof.

Definition: A formula in CNF is called pure if each clause has at most three literals and either all of them are negative or all of them are positive. The problem of deciding whether a pure formula is satis­ fiable is known to be NP-complete [Garey and John­ son, 1979] .

We next obtain a lemma concerning the complexity of model checking in default logic.

Lemma 2 For every n there is a default logic the­ ory .6-n = (Dn, Wn) such that to every pure formula F over n variables can be assigned (in polynomial time) a model mF that belongs to some extension of .6-n iff F is satisfiable.

• Proof: Assume that F( a 1 , ... , an) is a pure for­ mula. Our default theory will be formed over a set of variables c1, ... , Ck, b, z1, Zz, . .. , Zn, with k = 2( ~ ). To simplify the presentation we use X; to stand for the formula

b/\z1/\ . .. /\z;-1/\z;/\zi+1/\ ... 1\zn for 1 :S i :S n and Yi for

b/\z1/\ ... /\z;-1/\z;/\zi+I/\ ... 1\Zn for 1 :S i :S n Now we define a set D of defaults:

3 We thank Marco Cadoli for useful discussions on the issue of the size of representations.

For every positive clause C; = (a;, V a; 2 V a; 3 ) we introduce default dt:

For every negative clause C; =(a;, V a;, V a;a) we introduce default dJ:

For each clause C; we will also introduce a de­ fault d? = : c;/ c; . We take

Our lemma now follows directly from the fol­ lowing claim (details appear in full version of paper).

Set c; to 1 if C; is in F and to 0 other­ wise. Then F is satisfiable if and only if m = c1 c2 ... Ck 11 ... 1 is in some extension of {D, W). ·

Suppose now that for any default logic 6. there is a formula whose circumscription produces the same set as the union of extensions for 6.. Then by Lemma 2 we conclude that checking satisfiability of every pure formula of fixed size can be reduced to checking whether a given model belongs to cir­ cumscription of a fixed formula, which is in co-NP. (Note that to show that a model is not a minimal model, one simply has to provide a model that is contained in the original model). In other words, it would imply that NP~ co-NP /poly (the fixed formula is the advice a( n) in the definition of the P /poly etc. classes [Karp and Lipton, 1980]). ·

1. M Pj+DL unless the polynomial hierarchy col­ lapses.

We need the following lemina.

Lemma 3 Fix M to be any Turing machine that op­ erates in linear space. For every n there is a set of model preference defaults 6.n such that to every input x of length n we can assign {in polynomial time) a model m., such that m., is a model of 6.n if and only if M accepts x.

Proof: Assume without loss of generality that M, after accepting, restores its input tape to the initial con­ figuration (which it has saved) and starts its com­ putation anew on the same input; when it rejects, it halts. Suppose that there are at most 2k symbol­ state combinations in M, and p moves (each move is of the form "if three contiguous symbol-state combi­ nations are (a, b, c), then replace them by (a', b', c')". We can assume that in any reachable configuration only one such move applies. We shall represent any configuration of M with n tape squares as 2nk + p Boolean variables X;j, Yij, i = 1, ... , n, j = 1, ... , k and Zj, j = 1, ... p. The x variables will represent the tape contents; the y variables will ordinarily be equal to the x variables but will facilitate the im­ plementation of the moves; and the z variables will be ordinarily zero, unless a move is in progress, in which case the z variable corresponding to the move being implemented will be one.

We shall next define the set of defaults 6.n that simulates the moves of M. That is, if a configura­ tion C of M yields another C', then in the graph Gan there is an arc from bit vector C to bit vec­ tor C'. Suppose that the qth move of M is of the form (a,b,c) => (a',b',c'). Since the total number of symbols is at most 2k, we can think of a etc. as k-tuples of bits. Let Xr[a, b, c] be the set of literals stating that the values of X;j, with i = r- 1, r, r + 1 and j = 1, ... ,k, spell abc, and let Yr[a,b,c] be the set of literals stating that the values of Yii, i = r- 1, r, r + 1,j = 1, . .. , k spell abc. Then we add the following defaults to 6.n:

For each i, 1 < i < n, we have a default (xr[a,b,c],yr[a,b,c],z- zq) (this default sets the bit Zq that says "move q in progress"). We have 3k defaults that change, one-by-one, the y-bits cor­ responding to squares i- 1 to i + 1 from (a, b, c) to (a', b', c'), when ever move q is in progress (we omit the straightforward details of these defaults). Similarly, we have 3k more defaults that copy the (a', b', c') from the y bits back to the x bits. Finally, a default resets Zq to zero, whenever xr[a', b', c'], Yr[a', b', c'], and only Zq among the z'z is one: The move has been implemented.

Let x be an input of length n of M, and let m., be the starting configuration of M on input x (and the corresponding bit vector in our x, y , z variables). It is easy to see that the following holds: The part of the graph G an reachable from m., is either a cycle or a path, depending on whether M accepts the input or not.

Hence m., is a model of 6.n if and only if M accepts x, concluding the proof of the lemma. ·

Hence, if for any given set of model preference defaults there is an equivalent default theory (or autoepistemic logic theory, etc.), this would mean that there is a E2 method for simulating any polynomial-space machine, which would collapse the hierarchy (polynomial space includes all levels of the polynomial hierarchy).

Notice that we have not proved that D L '""'M P; we do not know how to directly simulate default theories by model preference defaults. However, in Section 5 we show something slightly weaker but almost as com­ pelling: M P can simulate any knowledge representation formalism whose model-checking problem is solvable in polynomial space by adding extra variables -and this includes default logic, autoepistemic logic, and a host of others [Gottlob, 1992; Eiter and Gottlob, 1993]. On the other hand, 4 holds even if adding extra variables is allowed (because polynomial space is very likely more powerful than any level of polynomial hierarchy), which gives evidence that M P is in some sense stronger than default logic.

4 Sublanguages of propositional logic

Although some of the following relations follow from well-known properties of propositional logic, proofs of all are provided for completeness.

5. H ftCM, H ftDNF

Proof: Let f(x1,X2, ... ,X2n) (x1 V x2)(x3 V x4) ... (x2n-1 V X2n)· This function is already given as a conjunction of n Horn clauses so it has a short representation in H . Notice that any set of characteristic models for f must contain the maximal models off and it is easy to see that f has 2n maximal models (for any i E{1, ... , n}we can take X2i-1 = 0, x2; = 1 or X2i-1 = 1, X2i-1 = 0) . The size of its DNF representation is also expo­ nential, because it is a monotone formula and any term we get by multiplying one variable from each clause is a prime implicant (so there are 2n prime implicants). So, f has a polynomial representation in H whereas every representation of f in C M or DN F is of exponential size. ·

6. CMftDNF

Proof: Let

f(xl,X2, ... ,X2n) (x1 V x2)(x3 V X4) . .. (x2n-1 V X2n)· Let k < n, and let 1 ~ i 1 < ... < ik ~ n be a given set of indices. Then we define the vector ef 1 ... ,ik to have bits i 1, ... , ik equal to 0 and all other bits equal to 1.

The set of characteristic models that generates f is

(it has 2n+1 vectors) . By the same line of reasoning as in the previous proof we can conclude that the DNF representation off will have exponential size.

·

7. CMftH, DNFftH

Proof sketch: [Kautz et al. , 1993] use the function f(xl, X2, ... , X2n) = (X! 1\ x2) V ... V (x2n-1 1\ X2n) to separate CM from H. f has a short DN F and CM representation. The function is dual to the function used in 5, and by applying the same idea we conclude that f must have an exponential size representation in CN F , and therefore in H. ·

8. CN F "-'>H , H "-'+CN F

Proof: Let M be a Horn set of models. We will prove that shortest CNF representing M must be a Horn formula. Suppose the shortest CNF representing M contains a non-Horn clause C. Then there is a Horn clause CH ~ C that can be entailed from M (see [Selman and Kautz, 1991; Selman and Kautz, 1996] for the proof) and we can put CHin the CNF instead of C (the set of models will not change). This gives an even shorter formula representing M; contradiction. ·

9. DN F "-'+CM

The proof is given in the full version of the paper. Note that since C M cannot represents all possible sets of models, we consider here only sets of models repre­ sentable in both formalisms. The relationship between DN F and CM has also been analyzed in [Khardon and Roth, 1994] in a slightly different setting.

Proof sketch: In the full version of the paper, we show how to construct a short CNF formula and a DNF formula directly from a given decision tree. It fol­ lows that each polynomial size decision tree has both a short DNF and a short CNF representation. Since there exist short DNF formulas that do not have a short CNF representation, it follows that there can­ not exist a short decision tree for such formulas , and thus DN F ftDT. Similarly, CN F ftDT . ·

Proof sketch: The first two relations follow directly from the definition of AC 3 . For the third obser­ vation, we can show that, given a set of charac­ teristic models M, one can construct a short for­ mula in AC 3 that represents M. From a result in [Hastad, 1986], it follows that the parity function does not have a short AC 3 representation. Since the parity function has a short encoding in P L , it follows that P L ftAC 3 . Combining 8. and 9. we get DN F ftCN F that AC 3 is a generalization of DN F we conclude that AC 3 ftC N F . Similarly, AC 3 is a generalization of H which combined with 5. gives AC 3 ftC N F . ·

5 Adding Extra Variables

In this section, we show that adding extra variables im­ proves the representational succinctness of certain for­ malisms. We state our results here without the proofs . Our first result shows that by introducing additional variables, Horn formulas can efficiently encode sets of characteristic models. This result should be contrasted with that obtained in [Kautz et al., 1993], where it is shown that without the introduction of extra variables there are sets of models that have short characteristic model encodings but no short Horn formula encoding.

Definition: For a set S of m-bit vectors and given number n ~ m we define projn(S) as the set of n-bit vectors x = (x1, ... , Xn) for which there exists a vector s = (s1 , ... , sm)ES such that x; = Sm-n+i for 1 ~ i ~ n.

Proposition 1 For every set M = {m1, ... , mk} of n­ bit characteristic models there is a set S with a Horn representation of size polynomial in n + k such that projn(S) = closure(M).

We can in fact also show that using additional vari­ ables is provably more powerful. That is, we can prove that by adding extra variables it is possible to represent sets that otherwise require an exponential representation in Hand CM.

Finally, we consider the power of model preference de­ faults, when we allow for additional variables. Here we obtain a surprisingly general result:

Proposition 2 Let A be any knowledge representation formalism such that the model-checking problem of A can be carried out in polynomial space in the number of vari­ ables and the size of the representation. Then for any knowledge base K in A on n variables and representa­ tion sizes there is a set of model preference defaults .6. of size at most polynomial in n + s such that the projection of the set of models of .6. to the original n variables is precisely the set of models of K.

As noted earlier, this result implies that by allowing for additional variables M P can simulate any knowledge representation formalism whose model-checking prob­ lem is solvable in polynomial space. Default logic and autoepistemic logic are just two examples of such for­ malisms [Gottlob, 1992; Eiter and Gottlob, 1993].

6 Conclusions

Knowledge representation formalisms are usually com­ pared with respect to their computational properties and expressive power . Expressive power is characterized in terms of what can and cannot be represented in a formal­ ism. Often little consideration is given to the question to what extent the formalisms allow for a compact en­ coding of information. We presented a series of results showing that systems with similar expressive power can differ dramatically in the size of the shortest encoding of certain kinds of information.

Fig. 1 summarizes our main results . Each upward ar­ row leads to a provably more succinct representation formalism. (Some results are based on certain stan­ dard complexity theoretic assumptions.) For example, we have shown that there exist sets of models with short (polynomial) encodings in default logic, but that can only be captured by exponential size circumscriptive the­ ories. On the other hand, however, any set of models with a compact encoding using circumscription can also be captured by a short default logic theory. One surpris­ ing aspect of our analysis is that we found many strict separations between formalisms. This suggests that suc­ cinctness is indeed useful dimension along which to com­ pare representation formalisms.