Descriptive complexity and the \(W\) hierarchy.

*(English)*Zbl 0897.03029
Beame, Paul W. (ed.) et al., Proof complexity and feasible arithmetics. Papers from the DIMACS workshop, Rutgers, NJ, USA, April 21–24, 1996. Providence, RI: American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 39, 119-134 (1998).

A parameterized language is a set of pairs of a binary string \(x\) and a natural number \(k\). Examples for parameterized languages are given by the set \(P_0\) of all pairs \((x,k)\) where \(x\) is (an appropriate code of) a graph which has a vertex cover of size \(k\), and by the set \(P_1\) of all pairs \((x,k)\) where \(x\) is a graph which has a clique of size \(k\). A parameterized language \(L\) belongs to the class FPT of fixed-parameter tractable languages iff there is a polynomial \(p\), a function \(f\) from the naturals to the naturals, and a Turing machine \(M\), where \(M\) decides on input \((x,k)\) in time \(f(k) \cdot p (| x|)\) whether \(x\) is in \(L\).

R. G. Downey and M. R. Fellows introduced in a previous paper [SIAM J. Comput. 24, 873-921 (1995; Zbl 0830.68063)] a reducibility \(\leq_m^{\text{fpt}}\) between parameterized problems, as well as a hierarchy \(\text{FPT}\subseteq W[1]\subseteq W[2] \subseteq \ldots\). of classes of parameterized languages. All these classes are closed downwards under \(\leq_m^{\text{fpt}}\), and consequently, unless the hierarchy collapses to one of its levels, a parameterized language which is \(\leq_m^{\text{fpt}}\)-hard for \(W[t]\) cannot be contained in FPT or in \(W[j]\) for \(j<t\). Hence the relative complexity of parameterized languages can be compared via relating them to the \(W\) hierarchy. For example \(P_1\) might be viewed as being more complex than \(P_0\), because \(P_0\) is in FPT, while \(P_1\) is \(\leq_m^{\text{fpt}}\)-complete for \(W[1]\). For background on parameterized complexity see R. G. Downey and M. R. Fellows’s forthcoming textbook: Parameterized complexity (1998).

As their main result, the authors show that for each \(t \geq 1\), the class \(W[t]\) is equal to the downward closure under \(\leq_m^{\text{fpt}}\) of the class of languages definable by formulae of the form \(\phi=(\exists U)\psi\) where \(U\) is a set variable and \(\psi\) is a first-order formula in prenex form with a leading \(\forall\)-quantifier and at most \(t-1\) quantifier alternations. Here a specific logic is considered where the intended models are binary strings, and a language \(L\) is definable by a formula \(\phi\) iff \(L\) contains exactly the strings which satisfy \(\phi\). For details see the references cited in the text and for background see H.-D. Ebbinghaus and J. Flum’s textbook: Finite model theory (1995; Zbl 0841.03014). In addition, the authors give an equivalent form of their characterization in terms of sequences of first-order formulae of some special form which depends on \(t\). Here, for a language \(L\) in \(W[t]\) the \(k\)th formula in the sequence defines the slice \(P_k := \{x : (x,k) \in L \}\) of \(L\). Finally, the characterization of the classes \(W[t]\) are applied for classifying some parameterized languages in the \(W\) hierarchy.

As noted by the authors, the characterization of the classes \(W[t]\) in terms of second-order logic over finite strings resembles Fagin’s and Stockmeyer’s characterizations of the class NP and the polynomial time hierarchy, respectively [see R. Fagin, Complexity of Comput., Proc. Symp. Appl. Math., New York City 1973, 43-73 (1974; Zbl 0303.68035), and L. Stockmeyer, Theor. Comput. Sci. 3, 1-22 (1977; Zbl 0353.02024)], as well as subsequent results on NP optimization problems obtained by C. Papadimitriou and M. Yannakakis [J. Comput. Syst. Sci. 43, No. 3, 425-440 (1991; Zbl 0765.68036)].

For the entire collection see [Zbl 0881.00033].

R. G. Downey and M. R. Fellows introduced in a previous paper [SIAM J. Comput. 24, 873-921 (1995; Zbl 0830.68063)] a reducibility \(\leq_m^{\text{fpt}}\) between parameterized problems, as well as a hierarchy \(\text{FPT}\subseteq W[1]\subseteq W[2] \subseteq \ldots\). of classes of parameterized languages. All these classes are closed downwards under \(\leq_m^{\text{fpt}}\), and consequently, unless the hierarchy collapses to one of its levels, a parameterized language which is \(\leq_m^{\text{fpt}}\)-hard for \(W[t]\) cannot be contained in FPT or in \(W[j]\) for \(j<t\). Hence the relative complexity of parameterized languages can be compared via relating them to the \(W\) hierarchy. For example \(P_1\) might be viewed as being more complex than \(P_0\), because \(P_0\) is in FPT, while \(P_1\) is \(\leq_m^{\text{fpt}}\)-complete for \(W[1]\). For background on parameterized complexity see R. G. Downey and M. R. Fellows’s forthcoming textbook: Parameterized complexity (1998).

As their main result, the authors show that for each \(t \geq 1\), the class \(W[t]\) is equal to the downward closure under \(\leq_m^{\text{fpt}}\) of the class of languages definable by formulae of the form \(\phi=(\exists U)\psi\) where \(U\) is a set variable and \(\psi\) is a first-order formula in prenex form with a leading \(\forall\)-quantifier and at most \(t-1\) quantifier alternations. Here a specific logic is considered where the intended models are binary strings, and a language \(L\) is definable by a formula \(\phi\) iff \(L\) contains exactly the strings which satisfy \(\phi\). For details see the references cited in the text and for background see H.-D. Ebbinghaus and J. Flum’s textbook: Finite model theory (1995; Zbl 0841.03014). In addition, the authors give an equivalent form of their characterization in terms of sequences of first-order formulae of some special form which depends on \(t\). Here, for a language \(L\) in \(W[t]\) the \(k\)th formula in the sequence defines the slice \(P_k := \{x : (x,k) \in L \}\) of \(L\). Finally, the characterization of the classes \(W[t]\) are applied for classifying some parameterized languages in the \(W\) hierarchy.

As noted by the authors, the characterization of the classes \(W[t]\) in terms of second-order logic over finite strings resembles Fagin’s and Stockmeyer’s characterizations of the class NP and the polynomial time hierarchy, respectively [see R. Fagin, Complexity of Comput., Proc. Symp. Appl. Math., New York City 1973, 43-73 (1974; Zbl 0303.68035), and L. Stockmeyer, Theor. Comput. Sci. 3, 1-22 (1977; Zbl 0353.02024)], as well as subsequent results on NP optimization problems obtained by C. Papadimitriou and M. Yannakakis [J. Comput. Syst. Sci. 43, No. 3, 425-440 (1991; Zbl 0765.68036)].

For the entire collection see [Zbl 0881.00033].

Reviewer: W.Merkle (Heidelberg)

##### MSC:

03C13 | Model theory of finite structures |

03D15 | Complexity of computation (including implicit computational complexity) |

03D10 | Turing machines and related notions |

03D20 | Recursive functions and relations, subrecursive hierarchies |

03D30 | Other degrees and reducibilities in computability and recursion theory |

03D80 | Applications of computability and recursion theory |

68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |

68Q25 | Analysis of algorithms and problem complexity |