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

parameterized complexityW-hierarchybounded weft circuitssymmetric gates

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 1222098 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• 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

(5)

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

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)