No label defined (Q4375789)

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\). \textit{R. G. Downey} and \textit{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 \textit{R. G. Downey} and \textit{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 \textit{H.-D. Ebbinghaus} and \textit{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 \textit{R. Fagin}, Complexity of Comput., Proc. Symp. Appl. Math., New York City 1973, 43-73 (1974; Zbl 0303.68035), and \textit{L. Stockmeyer}, Theor. Comput. Sci. 3, 1-22 (1977; Zbl 0353.02024)], as well as subsequent results on NP optimization problems obtained by \textit{C. Papadimitriou} and \textit{M. Yannakakis} [J. Comput. Syst. Sci. 43, No. 3, 425-440 (1991; Zbl 0765.68036)]. For the entire collection see [Zbl 0881.00033].