W-hierarchies defined by symmetric gates

DOI10.1007/S00224-008-9138-6MaRDI QIDQ970108zbMATH OpenOpenAlexWikidataFDO

Authors Jörg Flum, Danny Hermelin, Moritz Müller, Michael R. Fellows, Frances Rosamond

Publication date 10 May 2010

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-008-9138-6

zbMATH Keywords

bounded weft circuitsparameterized complexitysymmetric gatesW-hierarchy

Mathematics Subject Classification ID

Mathematical problems of computer architecture (68M07) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• A Purely Democratic Characterization of W[1]
• Parameterized circuit complexity and the \(W\) hierarchy
• Parameterized complexity of weighted satisfiability problems
• scientific article; zbMATH DE number 1114020
• Parameterized complexity of weighted satisfiability problems: decision, enumeration, counting

Cites work

• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• scientific article; zbMATH DE number 1222098 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Machine-based methods in parameterized complexity theory
• On the parameterized complexity of short computation and factorization
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Relating monotone formula size and monotone depth of Boolean functions
• The parameterized complexity of maximality and minimality problems

Cited in

(6)

• Parameterized circuit complexity and the \(W\) hierarchy
• Parameterized complexity classes defined by threshold circuits: using sorting networks to show collapses with W-hierarchy classes
• Parameterizations of hitting set of bundles and inverse scope
• Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems
• A Purely Democratic Characterization of W[1]
• Parameterized complexity classes defined by threshold circuits and their connection with sorting networks

This page was built for publication: W-hierarchies defined by symmetric gates

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