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

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

zbMATH Keywords

satisfiability problemweft-\(t\) circuits

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (20)

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

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)