Describing parameterized complexity classes

DOI10.1016/S0890-5401(03)00161-5zbMath1076.68031OpenAlexW1988772559MaRDI QIDQ1877556

Martin Grohe, Jörg Flum

Publication date: 19 August 2004

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0890-5401(03)00161-5

zbMATH Keywords

descriptive complexity theory

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items (23)

Backdoors to Normality for Disjunctive Logic Programs ⋮ Parameterized Parallel Computing and First-Order Logic ⋮ On the Equivalence among Problems of Bounded Width ⋮ Parameterized Complexity Classes under Logical Reductions ⋮ Parameterized complexity classes beyond para-NP ⋮ Unnamed Item ⋮ The parameterized space complexity of embedding along a path ⋮ Some lower bounds in parameterized \(\mathrm{AC}^{0}\) ⋮ Parameterised counting in logspace ⋮ Counting Small Induced Subgraphs with Hereditary Properties ⋮ Small vertex cover makes Petri net coverability and boundedness easier ⋮ Unnamed Item ⋮ Parameterized complexity of theory of mind reasoning in dynamic epistemic logic ⋮ Parameterized Bounded-Depth Frege Is Not Optimal ⋮ The parameterized complexity of maximality and minimality problems ⋮ Parameterized complexity of asynchronous border minimization ⋮ Strong Backdoors for Default Logic ⋮ On parameterized complexity of the multi-MCS problem ⋮ Parameterized Complexity Results for 1-safe Petri Nets ⋮ On the Descriptive Complexity of Color Coding ⋮ A multiparametric view on answer set programming ⋮ Backdoors to planning ⋮ On the space and circuit complexity of parameterized problems: classes and completeness

Cites Work

• Advice classes of parametrized tractability
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• Fixed-Parameter Tractability, Definability, and Model-Checking
• Weak Second‐Order Arithmetic and Finite Automata
• Resolution Is Not Automatizable Unless W[P Is Tractable]
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• Fixed-Parameter Tractability and Completeness I: Basic Results
• When is the evaluation of conjunctive queries tractable?
• Computer Science Logic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Describing parameterized complexity classes