zbMATH — the first resource for mathematics

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

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