contain large parts that are actually independent from KB**; second, we can give technicals**
result in a very simple way by using the compilability classes introduced in the next section. Assumption 1 **We consider only formulae whose size is less than or equal to that of the**
knowledge base.

All formalisms we consider satisfy the right-hand side distruibutivity of conjunction, that is, KB ⊢F φ ∧ µ if and only if KB ⊢F φ and KB ⊢F µ**. The assumption on the size**
of φ is not restrictive in this case, if φ **is a CNF formula.**

## 3. Compilability Classes

We assume the reader is familiar with basic complexity classes, such as P, NP and (uniform) classes of the polynomial hierarchy (Stockmeyer, 1976; Garey & Johnson, 1979). Here we just briefly introduce non-uniform classes (Johnson, 1990). In the sequel, C, C′**, etc. denote**
arbitrary classes of the polynomial hierarchy.

We assume that the input instances of problems are strings built over an alphabet Σ.

We denote with ǫ **the empty string and assume that the alphabet Σ contains a special** symbol \# to denote blanks. The length **of a string** x ∈ Σ
∗**is denoted by** |x|.

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(|x|) in constant time, where x **is the input string.**
Of course, the fact that A(|x|) 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 (Boppana & Sipser, 1990). 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 |A(n)| ≤ 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.

7