Parameterized Compilability

1 Introduction

Compilability. Many computational reasoning problems involve deciding whether or not a query is entailed by a knowledge base (or database). Such reasoning problems are often computationally intractable. A methodology for coping with this intractability is compilation (also called preprocessing), which involves translating a knowledge base into a form that allows for more efficient query processing. Compilation is appropriate for knowledge bases that remain stable over time and will be queried numerous times, even if the compilation itself cannot be performed efficiently, since the cost of the compilation will be amortized by the speed-up in query processing. Although recent years have seen many interesting results on compilation, the basic idea of simplifying a sequence of computations by preprocessing a set of useful values is as old as mathematics, as discussed in [Cadoli et al., 2002].

A systematic theory. A number of results in the nineties demonstrated non-compilability results, which show, for instance, that the knowledge bases of a particular knowledge representation formalism are not compilable to those of another formalism in which query processing can be performed in polynomial time. The initial results of this type, including

[Cadoli et al., 1996; 1997; 1999; Gogic et al., 1995], were based on ad hoc proofs that did not explicitly use a unified proof technique.

In [Cadoli et al., 2002], a robust theory of compilability was developed that made it possible to systematically organize knowledge representation formalisms according to their compilability, much in the way that classical complexity theory made it possible to systematically organize languages according to their (in)tractability. In particular, the theory of compilability provides a way to define, for every classical complexity class C, an analogous compilability class comp-C; the theory also provides a notion of reduction for use with the compilability classes comp-C. The compilability class comp-P, which is the analog of P (those languages decidable in polynomial time), contains those formalisms that are compilable to a second formalism in which query processing can be performed in polynomial time. In saying that a formalism is compilable to a second formalism, we mean (roughly) that for every knowledge base x of the first formalism, there is a knowledge base f(x) in the second formalism having the same answers to queries as x and such that the size of f(x) is always polynomial in the size of x. This "polynomial size" requirement models the intuition that compilation is only useful if it does not greatly increase the size of a knowledge base.

Demonstration that a formalism is in comp-P is a positive compilation result, analogous to demonstration that a language is in P, a positive tractability result. Likewise, demonstration that a formalism is comp-NP-hard is a negative compilation result and implies that the formalism is not in comp-P (under a complexity-theoretic assumption), just as demonstration that a language is NP-hard implies that the language is not in P (under the standard assumption that P ̸= NP).

First in [Cadoli et al., 2002; 2000] and later in other papers including [Liberatore, 1997; Liberatore and Schaerf, 2000; Liberatore, 2000; 2001], the theory of compilability presented in [Cadoli et al., 2002] was applied successfully to classify knowledge representation formalisms that have appeared in the artificial intelligence literature. In particular, a multitude of formalisms, including propositional logic, circumscription, and default logic, have been demonstrated to be contained in comp-P or complete for the analog comp-C of a standard complexity class C. The downside of these classification results is that many of them are negative, showing that a formalism is complete for the compilability version of an intractable complexity class, such as comp-NP or comp-co-NP.

Parameterized complexity. The abundance of negative compilability results mirrors a state of affairs in complexity theory: although many problems of interest can be classified according to the developed scheme of complexity classes (P, NP, co-NP, etc.), there is an abundance of negative results that show completeness or hardness for classes believed to be strictly larger than P. Because such generally intractable problems do need to be dealt with in practice, a number of theoretical frameworks have been developed to provide a finer analysis of hard problems than that offered by standard complexity theory. Examples of such frameworks include the theory of approximation algorithms and average-case analysis. A relatively recent alternative framework is parameterized complexity [Downey and Fellows, 1999b].

Parameterized complexity is a theory that, as with classical complexity theory and compilability theory, provides classes and a notion of reduction for categorizing objects. In the case of parameterized complexity, the objects categorized are parameterized languages: languages with instances consisting of two parts, a main part and a parameter. Many languages that have been classically studied can be viewed naturally as parameterized languages. For example, each instance of the VERTEX COVER problem can be viewed as consisting of a graph G as the main part, and a natural number k as the parameter; the question is to decide whether or not the graph G has a vertex cover of size at most k. Similarly, the INDEPENDENT SET problem may be viewed as a parameterized language: an instance is again a graph G paired with a natural number k, and the question is to decide whether or not the graph G has an independent set of size at least k.

The parameterized flavor of tractability is called fixedparameter tractability; formally, a parameterized language is fixed-parameter tractable (or, in the class FPT) if there exists a constant c such that for every k, instances with main part of size n and parameter k can be solved in time O(nc ). As an example, VERTEX COVER can be solved in time O(r k k2 +kn), where r is a constant, k is the parameter, and n is the size of the main part; consequently, for any fixed k, instances of VERTEX COVER with main part of size n and parameter k can be solved in time O(n), and so VERTEX COVER is considered to be fixed-parameter tractable. Because the running time of fixed-parameter tractable languages exhibits a restricted form of dependence on the parameter, such languages are often solvable in practice when the parameter falls into a limited range. (In fact, one can see from the given time bound for VERTEX COVER that this problem can be solved in polynomial time when the parameter k is O(logn).) On the other hand, INDEPENDENT SET is believed to require time where the main part exhibits an exponential dependence on the parameter - that is, a time of form similar to Ω(nk ). Indeed, INDEPENDENT SET is complete for a parameterized complexity class believed to properly contain FPT, and accordingly is believed to be outside of FPT.

Viewed classically, these two example languages are both NP-complete, and hence demonstrate that parameterized complexity is somewhat orthogonal to classical complexity; moreover, the example of VERTEX COVER indicates that parameterized complexity can provide tractability results where classical complexity does not. Indeed, the allowance of a non-polynomial dependence on the parameter of an input instance in fixed-parameter tractability permits the use of algorithmic ideas not utilized in proving standard polynomialtime tractability results, and the field of parameterized complexity has developed a rich and mathematically deep suite of algorithmic techniques.

Parameterized compilability. The contribution of this paper is parameterized compilability, a new theory of compilability incorporating the notion of parameterization as used in parameterized complexity. Our theory provides a novel set of concepts for proving compilability results, allowing the use of the sophisticated toolkit that has been developed for proving fixed-parameter tractability and intractability results, and provides an avenue for refining the many negative non-compilability results that have been proved using the established theory of compilability. As articulated in [Downey et al., 1999], one benefit of using a parameterized notion of computational tractability is that it becomes possible to engage in an extended dialogue with a single problem, by the investigation of a variety of parameters. We thus provide a theoretical framework in which we anticipate that the formulation and exploration of interesting parameters in the context of parameterized compilability will lead to refined analysis of compilability results.

The results in this paper are as follows. For every parameterized complexity class C, we define a compilability variant par-comp-C. We also define a notion of reduction for use with the par-comp-C classes, and demonstrate its robustness - in particular, that it is transitive and compatible (in a formal sense) with the classes par-comp-C. We also develop a general method for demonstrating hardness of a formalism for a class par-comp-C, and study the structure of the classes par-comp-C, relating this structure directly to the structure of non-uniform versions of parameterized complexity classes C.

2 Preliminaries

While we have attempted to make this paper as self-contained as possible, some familiarity with the basic notions of complexity theory (including non-uniform complexity classes), parameterized complexity, and compilability theory will be helpful; we name [Balc´azar et al., 1995], [Downey and Fellows, 1999b], and [Cadoli et al., 2002] as references for these topics, respectively. We also recommend the surveys [Downey and Fellows, 1999a; Downey et al., 1999] on parameterized complexity.

2.1 Definitions and Notation

Strings. We assume Σ to be a fixed finite alphabet that is used to form strings. The length of a string x is denoted by |x|. We will at times assume that pairs of strings (that is, elements of Σ∗ × Σ∗ ) are represented as strings (that is, elements of Σ∗ ) via a pairing function 〈·, ·〉. We make standard assumptions about this pairing function, namely, that the length of 〈x, y〉 is linear in |x| + |y|; 〈x, y〉 can be computed in time polynomial in |x| + |y|; there are polynomial-time computable projection functions π1, π2 : Σ∗ → Σ∗ such that π1(〈x, y〉) = x and π2(〈x, y〉) = y; and 〈·, ·〉 is lengthmonotone, that is, if |y| ≤ |z| then |〈x, y〉| ≤ |〈x, z〉| and |〈y, x〉| ≤ |〈z, x〉|. We also assume that there is a tripling function 〈·, ·, ·〉 for representing triples of strings as single strings, for which similar assumptions hold.

Functions. As usual, we consider a function p : N → N to be a polynomial if there exists a constant c ∈ N such that p(n) is O(nc ). A function p : N × Σ∗ → N is a parameterized polynomial if there exists a constant c ∈ N and a function h : Σ∗ → N such that for all (n, k) ∈ N × Σ∗ , p(n, k) ≤ h(k)(n + 1)c . In other words, p : N × Σ∗ → N is a parameterized polynomial if there exists a constant c ∈ N such that for each k ∈ Σ∗ , the function pk : N → N defined by pk(n) = p(n, k) is O(nc ).

A function f : Σ∗ → Σ∗ is polynomial-size if there exists a polynomial p : N → N such that for all x ∈ Σ∗ , |f(x)| ≤ p(|x|). Similarly, a function f : Σ∗ × Σ∗ → Σ∗ is parameterized polynomial-size if there exists a parameterized polynomial p : N × Σ∗ → N such that for all (x, k) ∈ Σ∗ × Σ∗ , |f(x, k)| ≤ p(|x|, k).

A function g : Σ∗ → Σ∗ is polynomial-time computable if there exist a polynomial p : N → N and a Turing machine M such that for all x ∈ Σ∗ , the Turing machine M, on input x, produces output g(x) in time less than p(|x|). Similarly, a function g : Σ∗×Σ∗ → Σ∗ is parameterized polynomial-time computable if there exist a parameterized polynomial p : N× Σ∗ → N and a Turing machine M such that for all (x, k) ∈ Σ∗ × Σ∗ , the Turing machine M, on input 〈x, k〉, produces output g(x, k) in time less than p(|x|, k).

A function h : Σ∗ → Σ∗ is recursively computable if there exists a Turing machine M such that for all x ∈ Σ∗ , the Turing machine M, on input x, produces output h(x).

Languages and ComplexityClasses. A language is a subset of Σ∗ , that is, a set of strings. A parameterized language is a subset of Σ∗ × Σ∗ , that is, a set of pairs of strings. A (parameterized) complexity class is a set of (parameterized) languages. When C is a (parameterized) complexity class and ≤ is a reduction, we say that C is compatible with ≤ if for all (parameterized) languages A and B, A ≤ B and B ∈ C imply that A ∈ C. Also, when C is a (parameterized) complexity class and ≤ is a reduction, we say that B is hard for C (alternatively, is C-hard) under ≤ reductions if for all A ∈ C, A ≤ B; and, we say that B is complete for C (alternatively, is C-complete) under ≤ reductions if B ∈ C and B is C-hard.

When C is a complexity class, the non-uniformversion (or "advice" version) of C, denoted by C/poly, contains those languages A such that there exists a polynomial-size function f : 1∗ → Σ∗ and a language B in C such that for all x ∈ Σ∗ , x ∈ A if and only if 〈f(1|x|), x〉 ∈ B. When C is a parameterized complexity class, the non-uniform version of C, denoted by C/ppoly, contains those parameterized languages A such that there exists a parameterized polynomialsize function f : 1∗ × Σ∗ → Σ∗ and a language B in C such that for all (x, k) ∈ Σ∗ ×Σ∗ , (x, k) ∈ A if and only if (〈f (1|x| , k), x〉, k) ∈ B.

When L is a parameterized language, define ϵL to be the set {(ϵ, y, k) : (y, k) ∈ L}.

Knowledge Representation Formalisms. A knowledge representation formalism (KRF) is a subset of Σ∗ × Σ∗ . A parameterized knowledge representation formalism (PKRF) is a subset of Σ∗ ×Σ∗ ×Σ∗ .

Conventions. We view a ternary function f : Σ∗ × Σ∗ × Σ∗ → Σ∗ as a binary function g : Σ∗ × Σ∗ → Σ∗ by pairing together the first two arguments, that is, g(〈x, y〉, z) = f(x, y, z). For example, a ternary function f : Σ∗ × Σ∗ × Σ∗ → Σ∗ is considered to be parameterized polynomial-size if there exists a parameterized polynomial p : N×Σ∗ → N such that for all (x, y, k) ∈ Σ∗ × Σ∗ × Σ∗ , |f(x, y, k)| ≤ p(|〈x, y〉|, k). Similarly, a PKRF F is viewed as a parameterized language by pairing together the first two strings of each triple, and so is considered to belong to a parameterized complexity class C if the language L = {(〈x, y〉, k) : (x, y, k) ∈ F} belongs to C.

For readability, we at times use a natural number m ∈ N in place of its unary representation 1m.

2.2 Compilability

In this subsection, we review the theory of compilability; the definitions and theorems of this subsection are all from [Cadoli et al., 2002], on which our presentation is based. Throughout this subsection, the following two assumptions concerning complexity classes and languages are in effect, just as in [Cadoli et al., 2002].

Assumption 1 Every complexity class C is compatible with and has complete problems under the polynomial-time manyone reduction ≤pm.

Assumption 2 In languages, suffixed blanks are considered to be irrelevant, that is, a string x□ is considered to be in a language A if x is in A.

For a KRF F , we will refer to each x ∈ π1(F ) as a knowledge base; a knowledge base x is considered to represent the knowledge {y ∈ Σ∗ : (x, y) ∈ F}. Roughly speaking, a KRF is considered to be compilable to a complexity class C if following a preprocessing of each knowledge base x, posing a query y to the knowledge base x - that is, deciding if (x, y) ∈ F - can be performed in C. The formal definition of those KRFs compilable to a complexity class C includes two ingredients. The first is a preprocessing function f; because preprocessing of a knowledge base is not useful if it greatly increases the size of the knowledge base, f is required to be of polynomial size. The second is a "target" KRF F ′ , mandated to be inside the class C, to which the KRF F is translated via the function f .

Definition 3 (comp-C) Let C be a complexity class. A KRF F belongs to comp-C if there exist

• a binary polynomial-size function f : Σ∗ × 1∗ → Σ∗ , and
• a KRF F ′ in C

such that for all pairs (x, y) ∈ Σ∗ ×Σ∗ ,

One can obtain a compilability class comp-C from any complexity class C. Hence, the comp-C classes offer a rich scheme by which one can classify KRFs, just as conventional complexity classes offer a rich scheme by which one can classify computational problems. Upon a first reading of Definition 3, it may be conceptually easiest for one to take the complexity class C to be equal to P (polynomial-time). In this case, the requirement that F ′ is in C means that queries (x, y) posed to F ′ can be processed efficiently, so f translates each F -knowledge base x - which is not necessarily in a form that allows for efficient resolution of queries (x, y) - into a F ′ -knowledge base f(x) - which is in a form that allows for efficient resolution of queries (x, y). 1

The following notion of reduction, associated with the comp-C classes, allows one to compare the compilability of different KRFs.

Definition 4 (comp reducibility) A KRF F is comp reducible to a KRF F ′ (denoted by F ≤comp F ′ ) if there exist

• binary polynomial-size functions f1, f2 : Σ∗ ×1∗ → Σ∗ and
• a binary polynomial-time computable function g : Σ∗ × Σ∗ → Σ∗

such that for all pairs (x, y) ∈ Σ∗ ×Σ∗ ,

Theorem 5 For every complexity class C, the comp reduction is transitive and is compatible with the class comp-C.

The structure of the compilability classes comp-C can be directly related to the structure of the complexity classes C/poly.

Theorem 6 Let C and C ′ be complexity classes. The containment comp-C ⊆ comp-C ′ holds if and only if the containment C/poly ⊆ C ′ /poly holds.

When C and C ′ are complexity classes that obey the proper containment C ⊊ C ′ , Theorem 6 gives strong evidence that the corresponding compilability classes comp-C and comp-C ′ obey a similar proper containment: comp-C ⊊ comp-C ′ . Note that in making this observation, we appeal to the widely held belief that relationships between "standard" complexity classes C, C ′ are not affected by non-uniformity, that is, C is properly contained in C ′ if and only if C/poly is properly contained in C ′ /poly. 2

1 This definition of comp-C is "non-uniform" in that the preprocessing or translation function f not only takes the knowledge base x as input, but in addition is given the length of the query y. A "uniform" version of the classes comp-C where the translation function f is only given the knowledge base x is studied and compared to the comp-C classes in [Cadoli et al., 2002]. In this paper, we present a non-uniform theory of parameterized compilability, and do not further discuss the uniform comp-C classes. One can use the ideas and concepts we present in this paper to develop a corresponding uniform theory.

2.3 Parameterized Complexity

Parameterized complexity is a theory for the classification of parameterized languages - languages whose constituents have two components. In classical complexity theory, the base complexity class modeling feasible computation is P, which is defined using the notion of polynomial-time; in parameterized complexity theory the base complexity class is FPT ("fixed-parameter tractable"), which is definable using the notion of parameterized polynomial-time.

Definition 7 (FPT) A parameterized language L belongs to the parameterized complexity class FPT if there exists a parameterized polynomial-time computable function g : Σ∗ × Σ∗ → {0, 1} such that for all pairs (x, k) ∈ Σ∗ × Σ∗ ,

Roughly speaking, a parameterized language L is in the class FPT if there exists a constant c ∈ N such that each "k-slice" Lk def = {x : (x, k) ∈ L} of L is computable in polynomial time via a polynomial of degree c. The degree of the polynomials bounding the time for Lk must be a "universal" constant c and cannot depend on k; on the other hand, the coefficients of these polynomials may have arbitrary dependence on k.

The following notion of reducibility may be used to compare the complexity of parameterized languages.

Definition 8 (parameterized reducibility) A parameterized language L is parameterized reducible to a parameterized language L′ (denoted by L ≤par L′ ) if there exist

• a parameterized polynomial-time computable function f : Σ∗ ×Σ∗ →Σ∗ , and
• a recursively computable function h : Σ∗ → Σ∗

such that for all pairs (x, k) ∈ Σ∗ ×Σ∗ ,

We now define two parameterized complexity classes. In contrast to the class FPT, each of these two classes is defined directly as those languages reducible to a particular language.

Definition 9 We define the following parameterized languages; the weight of a truth assignment is defined to be the number of variables it maps to true.

• WEIGHTED FORMULA SATISFIABILITY Input: A boolean formula F . Question: Does F have a satisfying assignment of

weight at most k?

• WEIGHTED CIRCUIT SATISFIABILITY Input: A boolean circuit C. Question: Does C have a satisfying assignment of

weight at most k?

2 Note that the term "non-uniformity" is intended here to take on the usual complexity-theoretic sense, as opposed to the slightly different sense in which comp-C was called non-uniform.

Definition 10 We define the following parameterized complexity classes.

• W[SAT] is the class of all parameterized languages that are parameterized reducible to WEIGHTED FORMULA SATISFIABILITY .
• W[P] is the class of all parameterized languages that are parameterized reducible to WEIGHTED CIRCUIT SATISFIABILITY .

It is straightforward to verify that the parameterized complexity classes defined here (FPT, W[SAT], and W[P]) are compatible with the parameterized reduction. Throughout this paper, we will assume that all discussed parameterized complexity classes have this property, and also that they have complete problems.

Assumption 11 Every parameterized complexity class C is compatible with and has complete problems under the parameterized reduction ≤par .

3 Parameterized Compilability

3.1 Classes and reductions

As with the theory of compilability, the starting point for the theory of parameterized compilability is the definition of compilability classes. Whereas a compilability version of each non-parameterized complexity class was defined (Definition 3), here we define a compilability version par-comp-C of each parameterized complexity class C.

As with the definition of comp-C, the definition of par-comp-C includes a translation function f with a space bound, as well as a "target" PKRF F ′ , which is required to be inside C.

Definition 12 Let C be a parameterized complexity class. A PKRF F belongs to par-comp-C if there exist

• a parameterized polynomial-size function f : Σ∗ ×1∗ × Σ∗ → Σ∗ , and
• a PKRF F ′ in C

such that for all triples (x, y, k) ∈ Σ∗ ×Σ∗ ×Σ∗ and natural numbers m ≥ |y|,

An implication of the containment of a PKRF F inside par-comp-C via the function f and the PKRF F ′ is the following. Define, for each k ∈ Σ∗ , the "k-slice" of a PKRF G to be Gk def = {(x, y) : (x, y, k) ∈ G}. Moreover, define fk : Σ∗ ×1∗ → Σ∗ to be the function fk(x, m) = f(x, m, k). Notice that for each k ∈ Σ∗ , the KRFs Fk, F ′k and the binary function fk satisfy the condition of Definition 3. That is, each k-slice Fk of F is compilable to the corresponding k-slice F ′k of F ′ by the function fk. Because the size of f is bounded by a parameterized polynomial, for k falling into a limited range, the functions fk will behave polynomially; likewise, when F ′ ∈ FPT, for k falling into a limited range, the KRF slices F ′k will have time complexity behaving polynomially.

Upon initial acquaintance, Definition 12 may appear to be complex. However, we believe that the classes par-comp-C unify the classes comp-C with parameterized complexity classes in a natural way. We substantiate this claim by considering two special cases of Definition 12, which may lend some intuition to the reader.

First, consider the case where the preprocessing function f simply returns as output its first argument, that is, f is equal to the projection π1. It follows that F must equal F ′ ; consequently, a PKRF F is contained in par-comp-C via such an f if and only if F is contained in C itself. Intuitively, the function f does not perform any preprocessing, so the compilability class par-comp-C simplifies out to the original class C. Next, consider the case where the PKRF F has the property that for all strings x, y, k, k′ ∈ Σ∗ , it holds that (x, y, k) ∈ F if and only if (x, y, k′ ) ∈ F; that is, F "ignores" the third component (the "parameter") of its strings. In this case, the PKRF F naturally induces a KRF ˜ F , defined to be

Such a PKRF F is contained in par-comp-FPT if and only if the induced KRF ˜ F is contained in comp-P. 3 In "ignoring" the parameter of the PKRF F, the compilability class par-comp-FPT simplifies out to its non-parameterized variant, namely, comp-P. We mention that by imposing the restrictions discussed in the two cases simultaneously, we effectively obtain the class P. Thus, one can think of FPT and comp-P as two different generalizations of P which are unified together in and can be obtained as specializations of par-comp-FPT.

We have the following notion of reducibility for comparing the compilability of PKRFs.

Definition 13 (par-comp reducibility) A PKRF F is parcomp-reducible to a PKRF F ′ (denoted by F ≤par comp F ′ ) if there exist

• parameterized polynomial-size functions f1, f2 : Σ∗ × 1∗ × Σ∗ → Σ∗ ,
• a parameterized polynomial-time function g : Σ∗ ×Σ∗ × Σ∗ → Σ∗ , and
• a recursively computable function h : Σ∗ → Σ∗

such that for all triples (x, y, k) ∈ Σ∗ ×Σ∗ ×Σ∗ and natural numbers m ≥ |y|,(x, y, k) ∈ F if and only if

We note that our definition of par-comp reducibility is not a direct analog of the definition of comp-reducibility; in Definition 13 the "preprocessing phase" f is given an upper bound m on the size of the query y, as opposed to the length of the query |y|, as in Definition 4. We believe that our notion of reduction is preferable because an assumption like Assumption 2 is not necessary to establish transitivity, and also because it allows for a simpler proof of transitivity. Our proof of transitivity can be specialized to a proof of transitivity for an "upper bound" variant of Definition 4 by removing the parameter k.

3 Sketch of one direction of this claim: suppose that the PKRF F is of the described form and in par-comp-FPT. Fix an arbitrary s ∈ Σ∗ , define the function ˜ f : Σ∗ × 1∗ → Σ∗ by ˜ f(x,m) = f(x,m, s), and define the KRF ˜ F ′ as {(x, y) : (x, y, s) ∈ F ′ }. It can be verified that ˜ F is contained in comp-P via ˜ f and ˜ F ′ .

Theorem 14 The par-comp reduction is transitive.

Theorem 15 For every parameterized complexity class C, the par-comp reduction is compatible with the class par-comp-C.

3.2 Completeness and Structure

We now study the notion of completeness for the classes par-comp-C, as well as the structure of the classes par-comp-C. First, we make a simple observation about the relationship between C/ppoly and par-comp-C which will aid us in our study.

Proposition 16 Let C be a parameterized complexity class. If the parameterized language A is in C/ppoly, then ϵA is in par-comp-C.

The following theorem, which will be of help in proving hardness of PKRFs, demonstrates that we can easily obtain complete languages for the class par-comp-C from complete languages for the underlying class C.

Theorem 17 Let C be a parameterized complexity class. If the parameterized language B is complete for C (under ≤par reductions), then ϵB is complete for par-comp-C (under ≤par comp reductions).

The next theorem is an analog of Theorem 6, and correspondingly provides strong evidence that the structure of the compilability classes par-comp-C reflects the structure of the parameterized complexity classes C.

Theorem 18 Let C and C ′ be parameterized complexity classes. The containment par-comp-C ⊆ par-comp-C ′ holds if and only if the containment C/ppoly ⊆ C ′ /ppoly holds.