Model-Checking Problems as a Basis for Parameterized Intractability

DOI10.2168/LMCS-1(1:2)2005MaRDI QIDQ5310633zbMATH OpenOpenAlexFDO

Authors Jörg Flum, Martin Grohe

Publication date 11 October 2007

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2168/lmcs-1(1:2)2005

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Specification and verification (program logics, model checking, etc.) (68Q60) Descriptive complexity and finite models (68Q19)

Recommendations

• scientific article; zbMATH DE number 2183396
• Fixed-parameter tractability, definability, and model-checking
• Parameterized circuit complexity and the \(W\) hierarchy
• scientific article; zbMATH DE number 1114020
• scientific article; zbMATH DE number 1222098

Cited in

(13)

• Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
• Intuitionistic implication makes model checking hard
• The parameterized space complexity of model-checking bounded variable first-order logic
• On the computational hardness based on linear fpt-reductions
• Hard problems on random graphs
• Machine characterizations for parameterized complexity classes beyond para-NP
• Machine-based methods in parameterized complexity theory
• Obtaining a proportional allocation by deleting items
• Bounded variable logic, parameterized logarithmic space, and Savitch's theorem
• Fixed-parameter tractability, definability, and model-checking
• Parameterized random complexity
• The complexity of first-order and monadic second-order logic revisited
• scientific article; zbMATH DE number 2183396 (Why is no real title available?)

This page was built for publication: Model-Checking Problems as a Basis for Parameterized Intractability

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