Parameterized circuit complexity and the W hierarchy

DOI10.1016/S0304-3975(96)00317-9MaRDI QIDQ1127315zbMATH OpenOpenAlexFDO

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

• 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
• 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?)
• 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)

• Threshold dominating sets and an improved characterization of \(W[2]\)
• On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
• 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
• Surfing with Rod
• A Purely Democratic Characterization of W[1]
• Parameterized Derandomization
• Confronting intractability via parameters
• scientific article; zbMATH DE number 7561704 (Why is no real title available?)
• Model-Checking Problems as a Basis for Parameterized Intractability
• Parameterized and Exact Computation
• Machine-based methods in parameterized complexity theory
• On the partial vertex cover problem in bipartite graphs -- a parameterized perspective
• Simplifying the weft hierarchy
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• W-hierarchies defined by symmetric gates
• The parameterized complexity of probability amplification

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)