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: https://drops.dagstuhl.de/opus/volltexte/2014/4836/
Berkholz, Christoph ; Elberfeld, Michael
Parameterized Complexity of Fixed Variable Logics
| pdf-format: |
|
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 | |
| Seminar: | 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) | |
| Issue date: | 2014 | |
| Date of publication: | 12.12.2014 |
