W-hierarchies defined by symmetric gates

DOI10.1007/s00224-008-9138-6zbMath1211.68217OpenAlexW2126048752WikidataQ57359767 ScholiaQ57359767MaRDI QIDQ970108

Danny Hermelin, Moritz Müller, Jörg Flum, Michael R. Fellows, Frances A. 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

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

Related Items (3)

Parameterized complexity classes defined by threshold circuits: using sorting networks to show collapses with W-hierarchy classes ⋮ Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems ⋮ Parameterizations of hitting set of bundles and inverse scope

Cites Work

• Machine-based methods in parameterized complexity theory
• On the parameterized complexity of short computation and factorization
• Relating monotone formula size and monotone depth of Boolean functions
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• The parameterized complexity of maximality and minimality problems
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Unnamed Item
• Unnamed Item

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