A Theory of Average-Case Compilability in Knowledge Representation
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 455-459.
© 2003 International Joint Conferences on Artificial Intelligence
Abstract
Compilability is a fundamental property of knowledge representation formalisms which captures how succinctly information can be expressed. Although many results concerning compilability have been obtained, they are all "worst-case" results. We develop a theory of average-case compilability which allows for the formal comparison and classification of knowledge representation formalisms "on average."
- [Balcazar et al., 1995] J. L. Balcazar and J. Dfaz and J. Gabarr6. Structural Complexity I. Springer-Verlag, Berlin, 1995.
- [Cadoli et al., 2000a] Marco Cadoli, Francesco M. Donini, Paolo Liberatore, and Marco Schaerf. Preprocessing of intractable problems. Information and Computation, 176(2):89-120, 2000.
- [Cadoli et al., 1999] Marco Cadoli, Francesco M. Donini, Paolo Liberatore, and Marco Schaerf. The size of a revised knowledge base. Artificial Intelligence, 115(1), 25~64.
- [Cadoli et al., 2000b] Marco Cadoli, Francesco M . Donini, Paolo Liberatore, and Marco Schaerf. Space Efficiency of Propositional Knowledge Representation Formalisms. Journal of Artificial Intelligence Research, 13:1-31, 2000.
- [Cadoli et al., 1997] Marco Cadoli, Francesco M. Donini, Marco Schaerf, and Riccardo Silvestri. On Compact Rep- resentations of Propositional Circumscription. In Theoret- ical Computer Science, 182:183-202.
- [Cadoli et al., 1996] Marco Cadoli, Francesco M. Donini, and Marco Schaerf. Is Intractability of Non-Monotonic Reasoning a Real Drawback? Artificial Intelligence, 88:215-251.
- [Gogic et al., 1995] Goran Gogic, Henry Kautz, Christos Pa- padimitriou, and Bart Selman. The Comparative Linguis- tics of Knowledge Representation. In Proceedings of the 14th International Joint Conference on Artificial Intelli- gence, pages 862-869, Montreal, Canada, 1995. IJCAI
- [Goldreich, 1997] Oded Goldreich. Notes on Levin's Theory of Average-Case Complexity. Electronic Colloquium on Computational Complexity (ECCC) 4(58): 1997.
- [Gurevich, 1991a] Yuri Gurevich. Average case complete- ness. Journal of Computer and System Sciences, 42:346- 398, 1991.
- [Gurevich, 1991b] Yuri Gurevich. Average case complexity. In Proceedings of the I 8th International Colloquium on Automata, Languages and Programming, volume 510 of Lecture Notes in Computer Science, Springer, pages 615- 628, 1991.
- [Gurevich, 1989] Yuri Gurevich. The challenger-solver game: variations on the theme of P =? NP. EATCS Bul- letin, pages 112-121, 1989.
- [lmpagliazzo, 1995] Russell Impagliazzo. A personal view of average-case complexity. In Proceedings of the lOth Conference on Structure in Complexity Theory, IEEE Computer Society Press, pages 134-147, 1995.
- [Johnson, 1984] David Johnson. The NP-completeness col- umn: an ongoing guide. Journal of Algorithms, 5:284-299, 1984.
- [Kautz et al., 1995] Henry Kautz, Michael Kearns, and Bart Selman. Horn approximations of empirical data. Artificial Intelligence, 75:129-145.
- [Khardon and Roth, 1996] Roni Khardon and Dan Roth. Reasoning with Models. Artificial Intelligence 87:187- 213, November 1996.
- [Levin, 1986] Leonid Levin. Average case complete prob- lems. SIAM Journal on Computing, 15:285-286, 1986.
- [Papadimitriou, 1996] Christos Papadimitriou. The Com- plexity of Knowledge Representation. In Proceedings of the Eleventh Annual IEEE Conference on Computational Complexity, pages 244-248, Philadelphia, Pennsylvania, May 1996.
- [Wang, 1997] Jie Wang. Average-case computational com- plexity theory. (L. Hemaspaandra and A. Selman, eds.), Complexity Theory Retrospective II, Springer-Verlag, pages 295-328, 1997.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
By now, a multitude of knowledge representation formalisms have been proposed and studied in the literature, for exam ple, propositional logic, default logic, and circumscription - to name a few. The comparison of these formalisms has been a major research theme over the past decade. In par ticular, many results have been obtained on the computa tional complexity of inference and model checking - core reasoning tasks associated with each formalism. The funda mental property of compilability, which measures how effi ciently or succinctly a formalism represents knowledge, has also been studied. 1 There is now a rich body of results concerning compilability; however, all of these results ad dress the "worst-case", and are thus susceptible to the com plaint that they do not address "average" or "typical" com pilability. The main contribution of this paper is a theoret ical framework providing a language and tools for compar ing and classifying the compilability of formalisms on aver age. Our framework is built on notions and insights from the theory of compilability clases due to Cadoli et a!. [2000a; 2000b] and the theory of average-case time complexity due to Levin [1986].
1.1 Background
Compilability. Informally, a formalism A is compilable to a formalism B if for every knowledge base x in formalism A, there is a knowledge base in formalism B representing the same information as x with size polynomial in the length of x. 2 Intuitively, this means that formalism B is at least as space efficient as formalism A: whatever can be expressed in formalism A can be expressed, with about the same level of succinctness, in formalism B.
1 In previous work, compilability has also been called space effi ciency and succinctness.
A number of papers compared the compilability of dif ferent formalisms [Kautz et al., 1995; Gogic et al., 1995; Khardon and Roth, 1996; Cadoli et al., 1996; 1997; 1999; 2000a; 200Gb]. In many cases, these papers rigorously prove that one formalism B is strictly more succinct than another formalism A - that is, A is compilable to B, but B is not compilable to A. This means that there is no way to trans late knowledge bases in B to knowledge bases in A, unless the translation is allowed to increase the size of knowledge bases by a super-polynomial amount. In other words, any translation of knowledge bases in B to knowledge bases in A is inherently exponential in size. 3 Observe that this state ment has the same flavor as the famous "P does not equal NP" conjecture from classical complexity theory. This conjecture holds that no algorithm can solve an NP-complete problem, unless the algorithm is allowed to take super-polynomial time on some inputs - or, put differently, any algorithm solving a NP-complete problem is inherently exponential in time.
Notice that the above definition of "formalism A is com pilable to formalism B" does not take into account the dif ficulty or complexity of computing the translation between knowledge bases in A and knowledge bases in B. This non uniformity is a key feature of the definition: the existence of a succinct translation is sufficient; an efficiently computable translation is not necessary. It turns out that many proofs of non-compilability - that is, proofs of statements of the form "formalism B is not compilable to formalism A" - rely on re sults from non-uniform complexity theory. Such proofs often are not unconditional, but are contingent upon the widely be lieved complexity-theoretic assumption that the polynomial hierarchy does not collapse. 4
2 In the technical portion of this paper, this definition will be cap tured formally by the :Snu-comp reducibility.
3 Here, by "exponential" we mean exceeding every polynomial infinitely often.
4 The polynomial hierarchy is a collection of complexity classes which includes P, NP, co-NP, and other classes which are in essence generalizations of these three classes. For the intents and purposes of this paper, this assumption can be thought of as being similar to the (perhaps better known) assumption that P does not equal NP. (In
Compilability classes. The initial papers that demonstrated non-compilability results [Kautz et at. , 1995; Gogic et at., 1995; Khardon and Roth, 1996; Cadoli et at., 1996; 1997; 1999] were based on ad hoc proofs, each of which iso lated two particular formalisms and then demonstrated non compilability of one to the other. In [Cadoli et at., 2000a; 2000b], new complexity classes measuring compilability, called compilability classes, were introduced; for every clas sical complexity class C, it is possible to define a compil ability class analog of C. The theory of compilability classes made it possible to systematize proofs of non-compilability much in the way classical complexity theory makes it pos sible to systematize proofs of intractability. A proof that a language is NP-complete is demonstration that there is no polynomial-time algorithm for the language, and that the lan guage has the same time complexity (up to a polynomial) as all other NP-complete languages. Likewise, a proof that a for malism is complete for the compilability class analog of NP is demonstration that it is not compilable to any formalism in the compilability class analog of P, and that the language is compilable to and from all other formalisms complete for the compilability class analog of NP. 5 (More generally, when C is a class from the polynomial hierarchy, a proof that a for malism is complete for the compilability class analog of C is demonstration that it is not compilable to any formalism in the compilability class analog of C', if C' is below C in the polynomial hierarchy.)
In addition to providing a methodology for comparing formalisms with respect to compilability, the compilability classes capture formally the notion of off-line preprocessing. Preprocessing a knowledge base off-line can be of great util ity if the resulting, processed knowledge base is in a form that allows for quick, on-line response to queries (and if many queries are expected). Membership of a formalism A in the compilability class analog of P will mean that any knowledge base x of A can be preprocessed into a form that does not un reasonably increase the size of x, but permits queries to x to be processed efficiently (that is, in polynomial time).
The compilability classes are part of a formal framework for discussing compilability, which includes robust notions of reduction and completeness. Not only is this framework extremely appealing from a theoretical point of view, but the compilability classes are rife with natural complete problems - the sine qua non of complexity classes purporting to be use ful in performing problem classification. Indeed, there do not appear to be any knowledge representation formalisms which defy classification as complete for a compilability class. On the downside, many of the existing classification results are quite negative, showing that a formalism is complete for (the compilability class analog of) NP, coNP, or a higher level of the polynomial hierarchy.
fact, if the polynomial hierarchy does not collapse, then P does not equal NP.)
5 0ur discussion presumes that the polynomial hierarchy does not collapse.
1.2 Motivations and Approach
Worst-case versus average-case. Although crisp theo retical results can be obtained concerning compilability and non-compilability, these are worst-case notions: non compilability of formalism B to formalism A implies that there is an infinite family of knowledge bases in B that can not be succinctly translated into knowledge bases in A. Non compilability does not say anything about the density or fre quency of instances from the family of untranslatable knowl edge bases. This observation calls into question the real world utility of studying compilability (as defined above); if formalism B is compilable to formalism A for all but a pathological family of knowledge bases arising infrequently in practice, then formalism B is, for pragmatic purposes, compilable to formalism A. Therefore, a theory which per mits formal results of compilability on average is necessary. This paper lays the foundations for a theory of average-case compilability.
Notice that our objection to the worst-case nature of non compilability is not truly novel. It has long been observed that NP-completeness of a language L does not imply hard ness of L on typical or real-world instances. Our objection is really this old observation, masquerading in the new context of compilability.
One theory that was developed in response to this old observation is the theory of average-case time complexity (ACTC), initiated by Levin [ 1986]. Our theory of average case compilability will be built on a key notion of ACTC - that of "polynomial on average." Moreover, there are useful analogies between our theory and the theory of ACTC. Con sequently, we provide a brief overview of ACTC.
Average-case time complexity. By definition, a language L (consisting of strings) is in P if there is an algorithm decid ing membership for L in polynomial time. The idea behind ACTC is to relax the requirement in this definition that a suit able algorithm is one that always runs in polynomial time; this is done by placing a probability distribution on all strings and allowing an algorithm to take super-polynomial times on unlikely strings.
A language paired with a probability distribution over all strings is called a distributional language. While languages are the objects classified by classical complexity theory, dis tributional languages are the objects classified by ACTC. A distributional language (L, J.L) is in the average-case version of P, average-P, if there is an algorithm deciding member ship for L in time polynomial on J.L-average - a concept to be discussed formally later in this paper.
There is a vast literature on ACTC; for more information, we recommend the overviews/surveys [Johnson, 1984; Gure vich, 1989; 1991a; 1991b; Impagliazzo, 1995; Wang, 1997; Goldreich, 1997] as starting points.
Average-case compilability. In laying down a theory for average-case compilability, we want to "soften" the definition of "formalism A is compilable to formalism B" by relaxing the requirement that there needs to be a translation of knowl edge bases of strictly polynomial size. This is done roughly in analogy to the described development of ACTC. We first de fine a distributional formalism to be a formalism paired with a probability distribution over all knowledge bases. Then, a distributional formalism (A, f..l) is (informally) compilable on average to a formalism B if there is a translation of knowl edge bases of size polynomial on f..L-average. 6
Using the notion of "compilable on average," we de fine average-case analogs of compilability classes. These average-case analogs contain distributional formalisms, in contrast to the compilability classes themselves, which con tain pure formalisms. Intuitively, membership of a distri butional formalism (A, f..l) in the average-case compilability class analog of P will mean the following: any knowledge base x of A can be preprocessed in a way that tends not to in crease the size of x by more than a polynomial (with respect to f..L), and that allows for rapid processing of queries to x.
2 Preliminaries
In this section, we present notation and assumptions that will be used throughout the paper.
We assume 1: to be a fixed finite alphabet which is used to form strings. We will at times assume that pairs of strings (that is, elements of 1:* x 1:*) are represented as strings (that is, elements of 1:*); when this assumption is made, we as sume that the representation is via a pairing function ( ·, ·) such that the length of (x, y) is linear in lxl + IYI· For a string x E 1:*, we let lxlu denote llxl, that is, the length of x written in unary notation.
We assume that the reader has familiarity with basic no tions of computational complexity theory - in particular, the classes of the polynomial hierarchy (P, NP, co-NP, 1:~, II~, etc.) and the polynomial many-one reduction ::;~ [Balcazar et al., 1995]. A language is a subset of 1:*, that is, a set of strings. A complexity class is a set of languages. When C is a complexity class and ::; is a reduction, we say that C is compatible with ::; if for all languages A and B, A ::; B and B E C imply that A E C. We will assume throughout that every complexity class C is compatible with the polynomial many-one reduction ::;~. We say that a language B is com plete for a complexity class C under ::; reductions if B E C and for all A E C, A ::; B.
A function f : 1:* --+ 1:* is polynomial-size if there exists a polynomial p such that for all x E 1:*, lf(x)l ::; p(lxl). A function f : 1:* --+ 1:* is polynomial-time computable if there exist a polynomial p and a Turing machine M such that for all x E 1:*, the Turing machine M, on input x, produces f(x) in time less than p(lx1). 7
Definition 2.1 A knowledge representation formalism ( KRF) is a subset of1:* x 1:*. When F is a KRF and x E 1:*, we let Fx denote the set {y E 1:* : (x, y) E F}.
Intuitively, each x E 1:* can be thought of as a knowledge base (KB), representing the information Fx. The following are examples of KRFs which capture model checking and in ference for 3-SAT formulas.
6 In the technical portion of this paper, this definition will be cap tured formally by the ::;dist-nu-comp reducibility.
7 Notice that every polynomial-time computable function is polynomial-size, but not every polynomial-size function is polynomial-time computable.
Propositional-Logic-Me ~r
Clause-Inference ~r
Notice the generality of the definition of a KRF; the knowl edge represented (the various Fx) may be models, formulas, or some altogether different combinatorial structures.
3 Compilability classes and reductions
This section reviews the theory of compilability classes. There are two different types of compilability classes, uni form and non-uniform, but our focus is on the latter, for rea sons discussed below. We emphasize that none of the defini tions, theorems, or insights in this section are our own, but rather; are due to [ Cadoli et al., 2000a; 2000b }, on which our presentation is based.
The formal definition of non-uniform compilability may by itself look non-intuitive, so we first attempt to describe some of the ideas behind this definition, before giving the actual definition. Intuitively, we want to say that a KRF F is compilable if membership queries y E Fx can be decided efficiently after the KB xis preprocessed into a new KB f(x). We want to constrain the size of the new KB f ( x); otherwise, it may be prohibitively large to store. We arrive at a candidate definition of compilability: say that a KRF F is in comp-C if for some polynomial-size function f and a second KRF F' E C, the property
holds. Notice that the class C constrains the difficulty of de ciding a post-processing query y E Ff(x); of course, such queries can be decided efficiently when C = P. However, to permit fine classification of KRFs, we leave Cas a parameter to the definition of comp-C.
The above definition misses one important detail - non uniformity. If F is a KRF such that Fx is always a finite set, F can never be complete for comp-C when C is a class of the polynomial hierarchy above P. At the same time, there are KRFs with this "finiteness" property that are prov ably not in comp-P. As an example, Clause-Inference is in comp-co-NP, but is neither comp-co-NP-complete nor in comp-P. 8 Hence, the classes comp-C fail to capture the com pi lability of some very natural KRFs. (For more informa tion on these matters, as well as proofs of the claims, we refer the reader to [Cadoli et al., 2000a].) To resolve this issue, we allow the length of a query to be known to the compilation mapping f.
Definition 3.1 (nu-comp-C) Let C be a complexity class. A KRF F belongs to nu-comp-C if there exists a binary polynomial-size function f : 1:* x 1 * --+ 1:* and a KRF F' in C such that the following property holds:
8 This discussion presumes that the polynomial hierarchy does not collapse.
The fact that the compilation mapping may use the length of y may seem a bit strange; after all, we wish to capture, after preprocessing on a knowledge base x , the difficulty of answering queries of the form y E Fx. However, it is rea sonable to assume that we will never be interested in such a query when the length of y greatly exceeds that of x - since such a query requires a large amount of time to even write down. Under this assumption, Definition 3.1 is equiv alent to the "uniform" definition given above. (Formally, if there exists a polynomial p such that (x, y) E F implies that IYI ~ p(lx l). then F is in nu-comp-C if and only ifF is in camp-C.)
The following notion of reduction, associated with the nu-comp-C classes, allows one to compare the compilability of different KRFs.
Definition 3.2 (nu-comp reducibility) A KRF F is nu-comp reducible to a KRF F' (denoted by F ~nu-comp F') if there exist binary polynomial-size functions h, h : ~· x 1 * --> ~· and a binary polynomial-time computable function g : ~· x ~· --> ~· such that the following property holds:
Theorem 3.3 The nu-comp reduction is transitive and is compatible with the class nu-comp-C (for every complexity class C).
We note that Clause-Inference is nu-comp-co-NP complete, under nu-comp reductions.
Finally, we observe that the nu-comp-C analog of the polynomial hierarchy does not collapse.
Theorem 3.4 If C1 and C2 are classes of the polynomial hi erarchy such that c2 is higher than clo then nu-comp-Cl is properly contained in nu-comp-C2 (under the assumption that the polynomial hierarchy does not collapse).
4 Average-case compilability
In this section, we present our new theory of average-case compilability.
Definition 4.1 A probability distribution J..L is a real valued function from ~· x 1 * to [0, 1] such that L(x,!)EE* x 1" J..L(X, l) = 1.
The nu-comp-C classes are used to classify and compare KRFs; our new classes will be used to classify and compare what we call distributional KRFs.
Definition 4.2 A distributional KRF (DKRF) is a pair (F, J..L) consisting of a KRF F and a probability distribution J..L.
We now define the notion of "polynomial on average." This definition is exactly that used in the theory of average-case time complexity (up to appropriate changes of the domain and range of the functions whose size we wish to measure).
Definition 4.3 Let J..L be a probability distribution. A function f ~· x 1 * --> ~· is of size polyno mial on J..L-average if there exists an E > 0 such that L (x, !)EE* x l" lf(x, l)l<l (x, l)I- 1 J..L(X, l) < oo.
We are now ready to define our new "average compilability" classes; formally, each class is a set of DKRFs. The definition can be viewed as a relaxation of Definition 3.1. The difference is that the translation mapping f : ~· x 1 * --> ~· need no longer be of strictly polynomial size, but is now only required to be of size polynomial on average.
Definition 4.4 (avg-nu-comp-C) Let C be a complexity class. A DKRF (F, J..L) belongs to avg-nu-comp-C if there exists a binary function f : ~· x 1 * --> ~· of size polynomial on J..L-average and a KRF F' in C such that the property of Definition 3.1 holds.
There is an alternative way to define avg-nu-comp-C, in terms of the following type of reduction, which relates DKRFs to KRFs.
Definition 4.5 (dist-nu-comp reducibility) A DKRF (F, J..L) is dist-nu-comp reducible to a KRF F' (denoted by F ~dist-nu-comp F') if there exist binary polynomial-size functions h, h : ~· x 1 * --> ~· and a binary polynomial time computable function g : ~· x ~· --> ~· such that (h, h) is of size polynomial on J..L-average 9 and the property of Definition 3.2 holds.
Theorem 4.6 Suppose that (F, J..L) is a DKRF and that Cis a complexity class. The DKRF (F, J..L) is in avg-nu-comp-C if and only if (F, J..L) ~dist-nu-comp F' for some F' in nu-comp-C.
This theorem has an important corollary: if nu-comp-C has a complete KRF F', then the DKRFs contained in avg-nu-comp-C are exactly those which reduce to F'. In or der to establish the corollary, the following lemma is needed.
Lemma 4.7 Suppose that (F, J..L) is a DKRF and that F' and F" are KRFs. lf(F, J..L) ~dist-nu-comp F' and F' ~nu-comp F", then (F, J..L) ~dist-nu-comp F".
Roughly, Lemma 4. 7 can be viewed as a proof of transitiv ity: if (F, J..L) reduces to F' and F' reduces to F", then (F, J..L) reduces to F" (under the right notions of reduction).
Corollary 4.8 Suppose that (F, J..L) is a DKRF, Cis a com plexity class and the KRF F' is nu-comp-C-complete un der nu-comp reductions. Then, the DKRF (F, J..L) is in avg-nu-comp-C if and only if(F, J..L) ~dist-nu-comp F'.
It is worth noting here that the class nu-comp-C has a complete KRF under nu-comp reductions whenever the un derlying complexity class C has a complete language under ~~reductions [Cadoli et al., 2000a].
We now give a notion of reduction for the comparison of DKRFs. When J..L and v are probability distributions, we say that v dominates J..L if there exists a polynomial p such that for all (x ,l) E ~· x 1*, J..L(x ,l) ~ p(l (x,l)l)v(x, l) .
Definition 4.9 (avg-nu-comp reducibility) A DKRF (F, J..L) is avg-nu-comp reducible to a DKRF (F', J..L 1 ) if there exist a nu comp reduction (h, h, g) from F to F' and a probability dis tribution J..Ll dominating J..L such that J..L 1 (y, m) ;::: L: J..L 1 ( x, l), where the sum is over all (x, l) such that fh(x , l) = y and there exists z E ~·with izl =land lg(h(x, l), z)l = m].
9 By (/1, /2), we denote the function which maps a pair (x , y) E E* x 1* to (/1 (x, y) , h(x, y) ).
Theorem 4.10 The avg-nu-comp reduction is transitive and is compatible with the class avg-nu-comp-C (for every com plexity class C).
5 Discussion
We now discuss some of the considerations behind the defi nitions in the previous section. When f-l : ~· x 1 * --+ [0, 1] is a probability distribution and S is a subset of ~· x 1 *, Jet (f.liS) denote the conditional distribution of f-l on S, that is, the function defined on (x, l) E S, with value equal to f.l(X, l) / [l:sES f.l(s)j .
- Why is Levin's notion of polynomial-on-average used in stead of the naive formulation of expected polynomial size?
According to the naive formulation, a function f : ~· x 1 * --+ ~* has expected polynomial size (with respect to f.J,) if there exists k 2: 1 such that for all n,
It is well known that this notion of expected polynomial is not closed under polynomials (see for example [Goldreich, 1997]). For instance, there exist functions J, f' : ~· x 1 * --+ ~· and a distribution f-l such that lf'(x, l)l = if(x, l)j2 and f has expected polynomial size, but f' fails to have expected polynomial size.
In our average-case compilability theory, this "lack of clo sure under polynomials" problem manifests itself in the fol lowing way. Suppose that, using the alternative definition of avg-nu-comp-C given in Theorem 4.6, the KRF F' is wit ness to the membership ofDKRF (F, f.l) in avg-nu-comp-C, that is, (F, f.l) :::;dist-nu-comp F'. Surely, ifF" is at least as space efficient as F' (that is, F' :::;nu-comp F"), then one ex pects that F" would also witness the membership of (F, f.l) in avg-nu-comp-C; this is the contentofLemma4.7, on which Corollary 4.8 relies. However, if expected polynomial size is used instead of polynomial on average in Definition 4.3, Lemma 4.7 breaks down - then, there would exist a DKRF (F, f.l) and KRFs F' and F" such that (F, f.l) :::;dist-nu-comp F', F' :::;nu-comp F", and (F, f.l) does not :::;dist-nu-comp reduce to F".
- Why does a DKRF have one probability distribution - over all elements of~· x 1 * - as opposed to an ensemble of distributions, each of which is over some finite subset of ~* X 1 *?
Defining a DKRF to be a KRF paired with an ensemble of distributions (each of which is, say, defined on a different string length) may seem more natural than the given defini tion, where there is only one distribution, on all strings.
However, the literature on ACTC contains many alterna tive formulations of "polynomial on average" (equivalent to that given in Definition 4.3) and sufficient conditions for a function to be polynomial on average. (For example, there is a different formulation of Definition 4.3 in terms of ensem bles of distributions, each having finite support, in [Impagli azzo, 1995].) These give rise to alternative formulations of avg-nu-comp-C, and so the particular characterizations we give for avg-nu-comp-C (in Definition 4.4 and Theorem 4.6) were, in some sense, chosen over provably equal characteri zations on purely aesthetic grounds.
- Why is a probability distribution over~* x 1 * as opposed to over~·? After all, the knowledge bases are represented by elements of~*, and an element of~* x 1 * is just a "slice" of a knowledge base.
Let F be a KRF conforming to the "bounded-query length" assumption discussed in Section 3, that is, suppose that there exists a polynomial p such that (x, y) E F implies IYI :::; p(jxi). Then, a distribution over~· naturally induces a distribution over ~· x 1 * for the padded version ofF defined as F' = {(x, z) : z = yOk, izl = p(jxi), (x, y) E F} (where 0 is an extra padding symbol), which has the property that all strings in F~ have the same length, for any x. Note that all of the example KRFs in this paper already have this property.
6 Example: model checking for circumscription
In this section, we illustrate the use of our new the ory by showing that model checking for circumscription on 3-SAT formulas (formalized below and denoted by Circumscription-Me( d)) is in avg-nu-comp-P, under a nat ural probability distribution where formulas are generated by including each clause independently with identical prob ability. Since Circumscription-MC(d) is nu-comp-co-NP hard, 10 this result gives a natural DKRF which is contained in avg-nu-comp-P, but which has a KRF which is provably not in nu-comp-P (Theorem 3.4).
Suppose that ¢ is a 3-SAT formula over Vn def {v1 , ... , vn}. and Sis a subset of Vn. We say that a model a : Vn --+ { 0, 1} of¢ is a S -minimal model (of¢) if for all other models b : Vn --+ {0, 1} of ¢, [b( s) :::; a( s) for all s E S] implies that [b( s) = a( s) for all s E S]. 11 In addition, a model a : S --+ {0, 1} of¢ is said to be a minimal model if it is the restriction of aS-minimal model a : Vn --+ {0, 1} (of ¢).
We define Circumscription-MC(d) to be the set
Let Wn denote the ¢ is a 3-SAT formula on Vn and a {0, 1} is an assignment)}, which tactically well-formed pairs that Circumscription-Me( d). set {¢ {vi,···, Vldnj} --+ is the set of all syn may or may not be in
Theorem 6.1 Let lln,c denote the distribution on 3-SAT for mulas over Vn where a formula is generated by including each of the 8 G) 3-clauses independently with probability cjn 2 (for all real numbers c > 0 and natural numbers n 2: 1). Let f.lc,d (with c > 0 and d E (0, 1)) be any dis tribution such that
- (f.lc,diWn) = lln,cfor all n, and
- f.lc ,d(¢, y) = 0 if¢ is a 3-SATformula on Vn and IYI =I ldnJ.
10 This can be shown using a result in [Gogic et at., 1995].
11 Here, ~ denotes the usual total ordering on {0, 1} where 0 ~ 1.
If the inequality 2 1 -de -c/ 6 (2 - e-cf 2 )d < 1 holds, then ( Circumscription-MC( d), /-Lc,d ) is in avg-nu-comp-P.
In particular, ( Circumscription-MC(0.9), p3.73,o.9) is in avg-nu-comp-P.
This theorem is established using techniques from proba bilistic combinatorics. It is worth noting that at c = 3. 73, the expected number of satisfying assignments that a random 3-SAT formula has is exponential.
7 Conclusions and future work
In [Papadimitriou, 1996], Papadimitriou writes:
The ultimate and most conclusive criterion for comparing knowledge representation formalisms is to compare their expressive power not on arbitrary sets of models, but on the "interesting" sets of mod els, the ones that come up in the "real world." We still hope that a meaningful and convincing formu lation of this important problem may be possible.
In this paper, we presented a robust and flexible theory of average-case compilability in which the intuitive notion of "interesting sets of models" can be formalized as a DKRF (Definition 4.2), DKRFs can be classified (Definition 4.4), and DKRFs can be compared (Definition 4.9). We illus trated the use of this theory by showing that, under a natural probability distribution, model checking for circumscription is compilable to the analog of the complexity class P, in our theory.
There are many open questions for future investigation; to conclude the paper, we list a few.
- Can additional DKRFs be classified as being inside avg-nu-comp-P? We conjecture in particular that Circumscription-MC(d)- along with the "standard" 3SAT probabilistic model with p = c/ n 2 for a sufficiently low c-is in avg-nu-comp-P.
- Are there DKRFs complete for avg-nu-comp-C (where Cis from the polynomial hierarchy) under the avg-nu comp reduction, or some other notion of reduction com patible with the avg-nu-comp-C classes?
- Can any questions concerning the new avg-nu-comp-C classes defined here be related to better known complexity-theoretic hypotheses?
@inproceedings{ijcai2003p68,
title = {A Theory of Average-Case Compilability in Knowledge Representation},
author = {Chen, Hubie},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob and Toby Walsh},
pages = {455--459},
year = {2003},
url = {https://ijcai.org/proceedings/2003/68},
}
TY - CPAPER TI - A Theory of Average-Case Compilability in Knowledge Representation AU - Chen, Hubie T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 455 EP - 459 UR - https://ijcai.org/proceedings/2003/68 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: