License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.109
URN: urn:nbn:de:0030-drops-48367
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4836/
Berkholz, Christoph ;
Elberfeld, Michael
Parameterized Complexity of Fixed Variable Logics
Abstract
We study the complexity of model checking formulas in first-order logic parameterized by the number of distinct variables in the formula. This problem, which is not known to be fixed-parameter tractable, resisted to be properly classified in the context of parameterized complexity. We show that it is complete for a newly-defined complexity class that we propose as an analog of the classical class PSPACE in parameterized complexity. We support this intuition by the following findings: First, the proposed class admits a definition in terms of alternating Turing machines in a similar way as PSPACE can be defined in terms of polynomial-time alternating machines. Second, we show that parameterized versions of other PSPACE-complete problems, like winning certain pebble games and finding restricted resolution refutations, are complete for this class.
BibTeX - Entry
@InProceedings{berkholz_et_al:LIPIcs:2014:4836,
author = {Christoph Berkholz and Michael Elberfeld},
title = {{Parameterized Complexity of Fixed Variable Logics}},
booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
pages = {109--120},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-77-4},
ISSN = {1868-8969},
year = {2014},
volume = {29},
editor = {Venkatesh Raman and S. P. Suresh},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4836},
URN = {urn:nbn:de:0030-drops-48367},
doi = {10.4230/LIPIcs.FSTTCS.2014.109},
annote = {Keywords: Parameterized complexity, polynomial space, first-order logic, pebble games, regular resolutions}
}
Keywords: |
|
Parameterized complexity, polynomial space, first-order logic, pebble games, regular resolutions |
Collection: |
|
34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) |
Issue Date: |
|
2014 |
Date of publication: |
|
12.12.2014 |