Descriptive complexity and the W hierarchy.
Rodney G. Downey, Michael R. Fellows, Kenneth W. Regan · 1996
The classes W [t] of the Downey-Fellows W hierarchy are defined, for each t, by fixed-parameter reductions to the weighted-assignment satisfiability problem for weft-t circuits. This paper proves that for each t ≥ 1, W [t] equals the closure under fixed-parameter reductions of the class of languages L definable by formulas of the form φ = (∃U)ψ, where U is a set variable and ψ is a first-order formula in � t prenex form. This is a fixed-parameter analogue of Fagin’s well-known characterization of NP by second-order existential formulas. An equivalent form of this result states that the fixed-parameter “slices ” Lk of L are definable by a family { φk} of first-order formulas in � t prenex form, subject to the restriction that the quantifier blocks in φk after the leading existential block are independent of k. Whether this restriction can be removed is connected to open problems in other recent papers on the W hierarchy.