Machine-based methods in parameterized complexity theory
We give machine characterizations of most parameterized complexity classes, in particular, of W[P], of the classes of the W-hierarchy, and of the A-hierarchy. For example, we characterize W[P] as the class of all parameterized problems decidable by a nondeterministic fixed-parameter tractable algorithm whose number of nondeterministic steps is bounded in terms of the parameter. The machine characterizations suggest the introduction of a hierarchy W-func between the W- and the A-hierarchy. We study the basic properties of this hierarchy. (c) 2005 Elsevier B.V. All rights reserved.
parameterized complexity machine characterizations complexity classes