Parameterized Complexity Classes under Logical Reductions

DOI10.1007/978-3-642-03816-7_23MaRDI QIDQ3182930zbMATH OpenOpenAlexWikidataFDO

Authors Anuj Dawar, Yuguo He

Publication date 16 October 2009

Published in Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03816-7_23

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• Parameterized Complexity and Logic
• Parameterized complexity of fixed variable logics
• Parameterized complexity classes beyond para-NP
• Describing parameterized complexity classes
• scientific article; zbMATH DE number 2086399
• Logical and schematic characterization of complexity classes
• Logics for complexity classes
• scientific article; zbMATH DE number 4103047
• Parameterized complexity and subexponential-time computability
• Parameterized proof complexity

Cites work

• scientific article; zbMATH DE number 3889514 (Why is no real title available?)
• scientific article; zbMATH DE number 4035805 (Why is no real title available?)
• scientific article; zbMATH DE number 1302020 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• Computer Science Logic
• Describing parameterized complexity classes
• Elements of finite model theory.
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fixed-parameter tractability, definability, and model-checking
• How many first-order variables are needed on finite ordered structures?
• Parametrized complexity theory.
• Relational queries computable in polynomial time
• Some Remarks on Generalized Spectra

Cited in

(5)

• Simplifying the weft hierarchy
• Parameterized and Exact Computation
• Parameterized complexity classes beyond para-NP
• Gap-languages and log-time complexity classes
• An analysis of the W*-hierarchy

This page was built for publication: Parameterized Complexity Classes under Logical Reductions

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