scientific article; zbMATH DE number 1114020

Authors Michael R. Fellows, Rodney G. Downey, Kenneth W. Regan

Publication date 11 October 1998

\(W\) hierarchy finite model theory fixed-parameter tractability parameterized complexity parametrized problems

Model theory of finite structures (03C13) Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Other degrees and reducibilities in computability and recursion theory (03D30) Applications of computability and recursion theory (03D80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Review text

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].

Recommendations

Cited in

(20)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4375789)