Parameterized Circuit Complexity and the W Hierarchy

Abstract

A parameterized problem ‹L,k› belongs to W[t] if there exists k’ computed from k such that ‹L,k› reduces to the weight-k’ satisfiability problem for weft-t circuits. We relate the fundamental question of whether the W[t] hierarchy is proper to parameterized problems for constant-depth circuits. We define classes G[t] as the analogues of AC0 depth-t for parameterized problems, and N[t] by weight-k’ existential quantification on G[t], by analogy with NP = э P. We prove that for each t, W[t] equals the closure under fixed-parameter reductions of N[t]. Then we prove, using Sipser's results on the AC0 depth-t hierarchy, that both the G[t] and the N[t] hierarchies are proper. If this separation holds up under parameterized reductions, then the W[t] hierarchy is proper. We also investigate the hierarchy H[t] defined by alternating quantification over G[t]. By trading weft for quantidiers we show that H[t] coincides with H[1]. We also consider the complexity of unique solutions, and show a randomized reduction from W[t] to Unique W[t].