Parameterized circuit complexity and the \(W\) hierarchy

DOI10.1016/S0304-3975(96)00317-9zbMath0896.68057MaRDI QIDQ1127315

Michael R. Fellows, Rodney G. Downey, Kenneth W. Regan

Publication date: 13 August 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

satisfiability problem; weft-\(t\) circuits

Mathematics Subject Classification ID

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Effective computation of immersion obstructions for unions of graph classes, Machine-based methods in parameterized complexity theory, The parameterized complexity of probability amplification, Threshold dominating sets and an improved characterization of \(W[2\)], The complexity of first-order and monadic second-order logic revisited, Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues], Parameterized random complexity, The Birth and Early Years of Parameterized Complexity, A Basic Parameterized Complexity Primer, Parameterized Derandomization

Cites Work

• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Matrix multiplication via arithmetic progressions
• NP is as easy as detecting unique solutions
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• Sparse parameterized problems
• Beyond NP-completeness for problems of bounded width (extended abstract)
• PP is as Hard as the Polynomial-Time Hierarchy
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item