Parameterized circuit complexity and the W hierarchy

DOI10.1016/S0304-3975(96)00317-9zbMATH Open0896.68057OpenAlexW1997639167MaRDI QIDQ1127315FDOQ1127315

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

Publication date 13 August 1998

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

Full work available at URL https://doi.org/10.1016/s0304-3975(96)00317-9

zbMATH Keywords

satisfiability problemweft-\(t\) circuits

Mathematics Subject Classification ID

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

Recommendations

• W-hierarchies defined by symmetric gates
• Machine-based methods in parameterized complexity theory
• Parameterized Complexity Classes under Logical Reductions
• scientific article; zbMATH DE number 1114020

Cites work

• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 503190 (Why is no real title available?)
• scientific article; zbMATH DE number 512804 (Why is no real title available?)
• scientific article; zbMATH DE number 1142303 (Why is no real title available?)
• scientific article; zbMATH DE number 1499087 (Why is no real title available?)
• scientific article; zbMATH DE number 806748 (Why is no real title available?)
• Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• Matrix multiplication via arithmetic progressions
• NP is as easy as detecting unique solutions
• PP is as Hard as the Polynomial-Time Hierarchy
• Sparse parameterized problems

Cited in

(20)

• Confronting intractability via parameters
• On the partial vertex cover problem in bipartite graphs -- a parameterized perspective
• The complexity of first-order and monadic second-order logic revisited
• Threshold dominating sets and an improved characterization of \(W[2]\)
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• Parameterized Derandomization
• Parameterized and Exact Computation
• A Purely Democratic Characterization of W[1]
• Simplifying the weft hierarchy
• The birth and early years of parameterized complexity
• Parameterized random complexity
• Model-Checking Problems as a Basis for Parameterized Intractability
• On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
• The parameterized complexity of probability amplification
• W-hierarchies defined by symmetric gates
• Machine-based methods in parameterized complexity theory
• A basic parameterized complexity primer
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• scientific article; zbMATH DE number 7561704 (Why is no real title available?)
• Surfing with Rod

This page was built for publication: Parameterized circuit complexity and the \(W\) hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1127315)