Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits

DOI10.1016/j.jcss.2005.06.003zbMath1110.68050OpenAlexW1542263829MaRDI QIDQ2581756

Mark Weyer, Martin Grohe, Jörg Flum

Publication date: 10 January 2006

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2005.06.003

zbMATH Keywords

Limited nondeterminismFixed-parameter tractability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Bounded fixed-parameter tractability and reducibility ⋮ Unnamed Item ⋮ Parameterized random complexity ⋮ Confronting intractability via parameters ⋮ Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic ⋮ The parameterized complexity of maximality and minimality problems ⋮ Slightly Superexponential Parameterized Problems ⋮ Hybridization Number on Three Rooted Binary Trees is EPT ⋮ Planar Capacitated Dominating Set Is W[1-Hard]

Cites Work

• Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete
• On the complexity of database queries
• On limited nondeterminism and the complexity of the V-C dimension
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• Fixed-Parameter Tractability, Definability, and Model-Checking
• Query evaluation via tree-decompositions
• New results on monotone dualization and generating hypergraph transversals
• Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
• Model-Checking Problems as a Basis for Parameterized Intractability
• Parameterized and Exact Computation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item