Model-Checking Problems as a Basis for Parameterized Intractability

DOI10.2168/LMCS-1(1:2)2005zbMath1125.68055OpenAlexW2950434194MaRDI QIDQ5310633

Martin Grohe, Jörg Flum

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) Specification and verification (program logics, model checking, etc.) (68Q60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items (6)

The complexity of first-order and monadic second-order logic revisited ⋮ Parameterized random complexity ⋮ Machine-based methods in parameterized complexity theory ⋮ On the computational hardness based on linear fpt-reductions ⋮ Obtaining a proportional allocation by deleting items ⋮ Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits

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