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 k❀**C, where C is a generic uniform complexity**
class, such as P, NP, coNP, or Σp 2
.

Definition 5 (k❀C classes) **A language of pairs** S ⊆ Σ
∗ × Σ
∗belongs to k❀C **iff there**
exists a binary poly-size function f **and a language of pairs** S
′ ∈ C such that for all hx, yi ∈ S
it holds:

## Hf(X, |Y|), Yi ∈ S ′Iff Hx, Yi ∈ 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 (Cadoli et al., 1996b). 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 |y| **as input, then such**
reduction is also impossible using a function taking x **only as its argument.** Theorem 1 (Cadoli, Donini, Liberatore, & Schaerf, 1997, Theorem 6) Let C be a class in the polynomial hierarchy and S ⊆ Σ
∗ × Σ
∗. A problem S **belongs to** k❀C if and only if there exists a poly-size function f **and a language of pairs** S
′**, such that for all**
hx, yi ∈ Σ
∗ × Σ
∗**it holds that:**
1. for all y such that |y| ≤ k, hf(x, k), yi ∈ S
′if and only if hx, yi ∈ S;
2. S
′ ∈ C.

Clearly, any problem whose time complexity is in C is also in k❀C: just take f(x, |y|) = x and S
′ = S**. What is interesting is that some problem in C may belong to** k❀C
′ **with**
C
′ ⊂ C, e.g.,, some problems in NP are in k❀**P. This is true for example for some problems**
in belief revision (Cadoli et al., 1999). In the rest of this paper, however, we mainly focus on "complete" problems, defined below. A pictorial representation of the class k❀**C is in**
Figure 1, where we assume that S
′ ∈ C.

For the problem pli no method proving that it belongs to k❀**P is known. In order**
to show that it (probably) does not belong to k❀**P, we define a notion of reduction and**
completeness. Definition 6 (Non-uniform comp-reducibility) Given two problems A and B, A is non-uniformly comp-reducible to B (denoted as A ≤nu−comp B**) iff there exist two poly-size**
binary functions f1 and f2, and a polynomial-time binary function g **such that for every**
pair hx, yi it holds that hx, yi ∈ A if and only if hf1(x, |y|), g(f2(x, |y|), y)i ∈ B.

The ≤nu−comp **reductions can be represented as depicted in Figure 2. Such reductions**
satisfy all important properties of a reduction.

Theorem 2 (Cadoli et al., 1996b, Theorem 5) The reductions ≤nu−comp satisfy transitivity and are compatible (Johnson, 1990) with the class k❀C **for every complexity class** C.