Compilability Classes

We assume the reader is familiar with basic complexity classes, such as P, NP and (uniform) classes of the polynomial hierarchy [49,17]. Here we just briefly introduce non-uniform classes [26]. In the sequel, C, ${\rm C}'$, etc. denote arbitrary classes of the polynomial hierarchy.

We assume that the input instances of problems are strings built over an alphabet $\Sigma$. We denote with $\epsilon$ the empty string and assume that the alphabet $\Sigma$ contains a special symbol $\char93$ to denote blanks. The length of a string $x \in \Sigma^*$ is denoted by $\vert x\vert$.

Definition 1  

An advice $A$ is a function that takes an integer and returns a string.

Advices are important in complexity theory because definitions and results are often based on special Turing machines that can determine the result of an oracle ``for free'', that is, in constant time.

Definition 2  

An advice-taking Turing machine is a Turing machine enhanced with the possibility to determine $A(\vert x\vert)$ in constant time, where $x$ is the input string.

Of course, the fact that $A(\vert x\vert)$ can be determined in constant time (while $A$ can be an intractable or even undecidable function) makes all definitions based on advice-taking Turing machine different from the same ones based on regular Turing machine. For example, an advice-taking Turing machine can calculate in polynomial time many functions that a regular Turing machine cannot (including some untractable ones).

Note that the advice is only a function of the size of the input, not of the input itself. Hence, advice-taking Turing machines are closely related to non-uniform families of circuits [3]. Clearly, if the advice were allowed to access the whole instance, it would be able to determine the solution of any problem in constant time.

Definition 3  

An advice-taking Turing machine uses polynomial advice if there exists a polynomial $p$ such that the advice oracle $A$ satisfies $\vert A(n)\vert \leq p(n)$ for any nonnegative integers $n$.

The non-uniform complexity classes are based on advice-taking Turing machines. In this paper we consider a simplified definition, based on classes of the polynomial hierarchy.

Definition 4  

If C is a class of the polynomial hierarchy, then C/ poly is the class of languages defined by Turing machines with the same time bounds as C, augmented by polynomial advice.

Any class C/poly is also known as non-uniform C, where non-uniformity is due to the presence of the advice. Non-uniform and uniform complexity classes are related: Karp and Lipton [27] proved that if NP $\subseteq$  P/poly then $\Pi^p_2 = \Sigma^p_2 =$ PH, i.e., the polynomial hierarchy collapses at the second level, while Yap [52] generalized their results, in particular by showing that if NP $\subseteq$  coNP/poly then $\Pi^p_3 = \Sigma^p_3 =$ PH, i.e., the polynomial hierarchy collapses at the third level. An inprovement of this results has been given by Köbler and Watanabe [33]: they proved that $\Pi^p_k \subseteq \Sigma^p_{k}/{\rm poly}$ implies that the polynomial hierarchy collapses to ZPP( $\Sigma^p_{k+1}$). The collapse of the polynomial hierarchy is considered very unlikely by most researchers in structural complexity.

We now summarize some definitions and results proposed to formalize the compilability of problems [6], adapting them to the context and terminology of PKR formalisms. We remark that it is not the aim of this paper to give a formalization of compilability of problems, or to analyze problems from this point of view. Rather, we show how to use the compilability classes as a technical tool for proving results on the relative efficiency of formalisms in representing knowledge in little space.

Several papers in the literature focus on the problem of reducing the complexity of problems via a preprocessing phase [30,28,32]. This motivates the introduction of a measure of complexity of problems assuming that such preprocessing is allowed. Following the intuition that a knowledge base is known well before questions are posed to it, we divide a reasoning problem into two parts: one part is fixed or accessible off-line (the knowledge base), and the second one is varying, or accessible on-line (the interpretation/formula). Compilability aims at capturing the on-line complexity of solving a problem composed of such inputs, i.e., complexity with respect to the second input when the first one can be preprocessed in an arbitrary way. In the next section we show the close connection between compilability and the space efficiency of PKR formalisms.

A function $f$ is called poly-size if there exists a polynomial $p$ such that for all strings $x$ it holds $\vert f(x)\vert \leq p(\vert x\vert)$. An exception to this definition is when $x$ represents a number: in this case, we impose $\vert f(x)\vert \leq p(x)$. As a result, we can say that the function $A$ used in advice-taking turing machine is a polysize function.

A function $g$ is called poly-time if there exists a polynomial $q$ such that for all $x$, $g(x)$ can be computed in time less than or equal to $q(\vert x\vert)$. These definitions easily extend to binary functions as usual.

We define a language of pairs $S$ as a subset of $\Sigma^* \times \Sigma^*$. This is necessary to represent the two inputs to a PKR reasoning problem, i.e., the knowledge base (KB), and the formula or interpretation. As an example, the problem of Inference in Propositional Logic (PLI) is defined as follows.

$$% latex2html id marker 1003 {\sc pli}= \{ \langle x, y \ra... ...ormulae (the KB), } y \mbox{ is a formula, and } x \vdash y \}$$

It is well known that PLI is coNP-complete, i.e., it is one of the ``hardest'' problems among those belonging to coNP. Our goal is to prove that PLI is the ``hardest'' theorem-proving problem among those in coNP that can be solved by preprocessing the first input in an arbitrary way, i.e., the KB. To this end, we introduce a new hierarchy of classes, the non-uniform compilability classes, denoted as $\parallel\!\leadsto$ C, where C is a generic uniform complexity class, such as P, NP, coNP, or $\Sigma^p_2$.

Definition 5 ( $\parallel\!\leadsto$ C classes)  

A language of pairs $S \subseteq \Sigma^* \times \Sigma^*$ belongs to $\parallel\!\leadsto$ C iff there exists a binary poly-size function $f$ and a language of pairs $S' \in {\rm C}$ such that for all $\langle x, y \rangle \in S$ it holds:

$$\langle f(x,\vert y\vert), y \rangle \in S' \mbox{ iff } \langle x, y \rangle \in S$$

Notice that the poly-size function $f$ takes as input both $x$ (the KB) and the size of $y$ (either the formula or the interpretation). This is done for technical reason, that is, such assumption allows obtaining results that are impossible to prove if the function $f$ only takes $x$ as input [6]. Such assuption is useful for proving negative results, that is, theorems of impossibility of compilation: indeed, if it is impossible to reduce the complexity of a problem using a function that takes both $x$ and $\vert y\vert$ as input, then such reduction is also impossible using a function taking $x$ only as its argument.

Theorem 1   [7, Theorem 6] Let $C$ be a class in the polynomial hierarchy and $S \subseteq \Sigma^* \times \Sigma^*$. A problem $S$ belongs to $\parallel\!\leadsto$ C if and only if there exists a poly-size function $f$ and a language of pairs $S'$, such that for all ${\langle x, y \rangle }\in \Sigma^* \times \Sigma^*$ it holds that:

1. for all $y$ such that $\vert y\vert \le k$, ${\langle f(x,k), y \rangle } \in S'$ if and only if ${\langle x, y \rangle } \in S$;

2. $S' \in$ C.

Clearly, any problem whose time complexity is in C is also in $\parallel\!\leadsto$ C: just take $f(x,\vert y\vert)=x$ and $S'=S$. What is interesting is that some problem in C may belong to $\mbox{$\parallel\!\leadsto$}{\rm C}'$ with ${\rm C}' \subset C$, e.g.,, some problems in NP are in $\parallel\!\leadsto$ P. This is true for example for some problems in belief revision [8]. In the rest of this paper, however, we mainly focus on ``complete'' problems, defined below. A pictorial representation of the class $\parallel\!\leadsto$ C is in Figure 1, where we assume that $S' \in C$.

For the problem PLI no method proving that it belongs to $\parallel\!\leadsto$ P is known. In order to show that it (probably) does not belong to $\parallel\!\leadsto$ P, we define a notion of reduction and completeness.

Figure: A representation of $\parallel\!\leadsto$ C.

Definition 6 (Non-uniform comp-reducibility)  

Given two problems $A$ and $B$, $A$ is non-uniformly comp-reducible to $B$ (denoted as $A \leq_{nu-comp}B$) iff there exist two poly-size binary functions $f_1$ and $f_2$, and a polynomial-time binary function $g$ such that for every pair ${\langle x, y \rangle }$ it holds that ${\langle x, y \rangle } \in A$ if and only if ${\langle f_1(x,\vert y\vert), g(f_2(x,\vert y\vert),y) \rangle } \in B$.

The $\leq_{nu-comp}$ reductions can be represented as depicted in Figure 2.

Figure 2: The nu-comp-C reductions.

Such reductions satisfy all important properties of a reduction.

Theorem 2   [6, Theorem 5] The reductions $\leq_{nu-comp}$ satisfy transitivity and are compatible [26] with the class $\parallel\!\leadsto$ C for every complexity class  C.

Therefore, it is possible to define the notions of hardness and completeness for $\parallel\!\leadsto$ C for every complexity class C.

Definition 7 ( $\parallel\!\leadsto$ C-completeness)   Let $S$ be a language of pairs and C a complexity class. $S$ is $\parallel\!\leadsto$ C -hard iff for all problems $A \in$  $\parallel\!\leadsto$ C we have that $A \leq_{nu-comp}S$. Moreover, $S$ is $\parallel\!\leadsto$ C -complete if $S$ is in $\parallel\!\leadsto$ C and is $\parallel\!\leadsto$ C -hard.

We now have the right complexity class to completely characterize the problem PLI. In fact PLI is $\parallel\!\leadsto$ coNP-complete [6, Theorem 7]. Furthermore, the hierarchy formed by the compilability classes is proper if and only if the polynomial hierarchy is proper [6,27,52] -- a fact widely conjectured to be true.

Informally, we may say that $\parallel\!\leadsto$ NP-hard problems are ``not compilable to P'', as from the above considerations we know that if there exists a preprocessing of their fixed part that makes them on-line solvable in polynomial time, then the polynomial hierarchy collapses. The same holds for $\parallel\!\leadsto$ coNP-hard problems. In general, a problem which is $\parallel\!\leadsto$ C-complete for a class C can be regarded as the ``toughest'' problem in C, even after arbitrary preprocessing of the fixed part. On the other hand, a problem in $\parallel\!\leadsto$ C is a problem that, after preprocessing of the fixed part, becomes a problem in C (i.e., it is ``compilable to C'').

We close the section by giving another example of use of the compilability classes through the well-known formalism of Circumscription [41]. Let $x$ be any propositional formula. The minimal models of $x$ are the truth assignments satisfying $x$ having as few positive values as possible (w.r.t.
set containment). The problem we consider is: check whether a given model is a minimal model of a propositional formula. This problem, called Minimal Model checking (MMC), can be reformulated as the problem of model checking in Circumscription, which is known to be co-NP-complete [4].

If we consider the knowledge base $x$ as given off-line, and the truth assignment $y$ as given on-line, we obtain the following definition:

$$\mbox{{\sc mmc}} = \{ \langle x,y \rangle ~\vert~ \mbox{$y$\ is a minimal model of $x$\ } \}$$

This problem can be shown to be $\parallel\!\leadsto$ coNP-complete [6, Theorem 13]. Hence, it is very unlikely that it can be in $\parallel\!\leadsto$ P; that is, it is very unlikely that there exists some off-line processing of the knowledge base, yielding (say) some data structure $x'$, such that given $y$, it can now checked in polynomial time whether $y$ is a minimal model of $x$. This, of course, unless $x'$ has exponential size. This observation applies also when $x'$ is a knowledge base in Propositional Logic, and led to the interpretation that Circumscription is more compact, or succint, than PL [9,21]. Our framework allows to generalize these results for all PKR formalisms, as shown in the sequel.