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/
Go to the corresponding LIPIcs Volume Portal

Berkholz, Christoph ; Elberfeld, Michael

Parameterized Complexity of Fixed Variable Logics

pdf-format:
12.pdf (0.5 MB)

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI