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 (1980) proved that if NP ⊆ **P/poly then Π**p 2 = Σp 2 **= PH, i.e., the polynomial hierarchy collapses at the second level, while Yap (1983) generalized their results, in particular**
by showing that if NP ⊆ **coNP/poly then Π**p 3 = Σp 3 **= PH, i.e., the polynomial hierarchy**
collapses at the third level. An inprovement of this results **has been given by K¨obler and**
Watanabe (1998): they proved that Πpk ⊆ Σ
p k
/poly implies that the polynomial hierarchy collapses to ZPP(Σpk+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 (Cadoli et al., 1996b), 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 (Kautz & Selman, 1992; Kautz et al., 1995; Khardon & Roth, 1997). 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 |f(x)| ≤ p(|x|). An exception to this definition is when x **represents a number:**
in this case, we impose |f(x)| ≤ 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(|x|**). These definitions easily extend to**
binary functions as usual.

We define a language of pairs S **as a subset of Σ**∗ × Σ
∗**. 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.

pli = {hx, yi | x is a set of propositional formulae (the KB), y **is a formula, and** x ⊢ 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-