PARAMETERIZED CIRCUIT COMPLEXITY AND THE W-HIERARCHY

A parameterized problem (L,k) belongs to W[t] if there exists k' compu ted from k such that (L, k) reduces to the weight-k' satisfiability pr oblem for weft-t circuits. We;elate the fundamental question of whethe r the W[t] hierarchy is proper to parameterized problems for constant- depth circuits. We define classes G[t] as the analogues of AC(0) depth -t for parameterized problems, and N[t] by weight-k' existential quant ification on G[t], by analogy with NP = There Exists.P. We prove that for each t, W[t] equals the closure under fixed-parameter reductions o f N[t]. Then we prove, using Sipser's results on the AC(0) depth-t hie rarchy, that both the G[t] and the N[t] hierarchies are proper. If thi s separation holds up under parameterized reductions, then the W[t] hi erarchy is proper. We also investigate the hierarchy H[t] defined by a lternating quantification over G[t]. By trading weft for quantifiers w e 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 Uniq ue W[t].