Parameterized circuit complexity and the W hierarchy

@article{citeulike:1584757, 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 = [there exists] [middle dot] 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 quantifiers 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].}, author = {Downey, Rodney G. and Fellows, Michael R. and Regan, Kenneth W. }, citeulike-article-id = {1584757}, doi = {http://dx.doi.org/10.1016/S0304-3975(96)00317-9}, journal = {Theoretical Computer Science}, keywords = {algorithms, complexity, logic}, month = {January}, number = {1-2}, pages = {97--115}, posted-at = {2007-08-23 06:25:21}, priority = {2}, title = {Parameterized circuit complexity and the W hierarchy}, url = {http://dx.doi.org/10.1016/S0304-3975(96)00317-9}, volume = {191}, year = {1998} }

TY - JOUR ID - citeulike:1584757 L3 - citeulike-article-id:1584757 N2 - 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 = [there exists] [middle dot] 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 quantifiers 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]. IS - 1-2 JF - Theoretical Computer Science EP - 115 TI - Parameterized circuit complexity and the W hierarchy VL - 191 SP - 97 KW - algorithms KW - complexity KW - logic AU - Downey, Rodney AU - Fellows, Michael AU - Regan, Kenneth PY - 1998/01/30/ UR - http://dx.doi.org/10.1016/S0304-3975(96)00317-9 ER -