An analysis of the W*-hierarchy. (English) Zbl 1122.03040

The well-known W-hierarchy was introduced by Downey and Fellows as a hierarchy of fixed-parameter intractable problems. The W*-hierarchy, introduced by Downey, Fellows, and Taylor, is a variant of the W-hierarchy. In this paper, it is shown that \(\text{W}[t]\subseteq \text{W}^*[t]\subseteq \text{W}[2t-2]\) for each \(t\geq 2\). Thus, the union over the levels of the W-hierarchy and over the W*-hierarchy, respectively, are the same. It was known before that \(\text{W}[1]\subseteq \text{W}^*[1]\) and \(\text{W}[2]\subseteq \text{W}^*[2]\). The other main result of the paper is a new logical characterization of the W*-hierarchy in terms of “Fagin-definable problems”. As a by-product, Chen, Flum and Grohe obtain an improvement of their earlier characterization of the W*-hierarchy in terms of model-checking problems. Furthermore, they obtain new complete problems for the classes W[3] and W*[3].


03D15 Complexity of computation (including implicit computational complexity)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI


[1] DOI: 10.1016/S0304-3975(97)00101-1 · Zbl 0912.68075
[2] DOI: 10.1016/0304-3975(94)00097-3 · Zbl 0873.68059
[3] DOI: 10.1137/S0097539792228228 · Zbl 0830.68063
[4] Theory of Computing Systems
[5] Die W*-Hierarchie (2005)
[6] Parameterized complexity (1999) · Zbl 0943.03029
[7] Parameterized complexity theory (2006)
[8] DOI: 10.1137/S0097539799360768 · Zbl 0992.68060
[9] Combinatorics, complexity, and logic–proceedings of DMTCS ’96 pp 194– (1996) · Zbl 0911.05001
[10] Proof complexity andfeasible arithmetic 39 pp 119– (1998)
[11] Logical Methods in Computer Science 1 (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.