Most parameterized complexity classes are defined in terms of aparameterized version of the Boolean satisfiability problem (theso-called weighted satisfiability problem). For example, Downey andFellow's W-hierarchy is of this form. But there are also classes, for example,the A-hierarchy, that are more naturally characterised in terms ofmodel-checking problems for certain fragments of first-order logic.Downey, Fellows, and Regan (1998) were the first to establish aconnection between the two formalisms by giving a characterisation of theW-hierarchy in terms of first-order model-checking problems. We improve their result and then prove a similar correspondence between weightedsatisfiability and model-checking problems for the A-hierarchy and theW*-hierarchy. Thus we obtain very uniform characterisations of manyof the most important parameterized complexity classes in both formalisms.Our results can be used to give new, simple proofs of some of the core resultsof structural parameterized complexity theory.
展开▼
