Abstract
Descriptive complexity theory aims at inferring a problem's computational complexity from the syntactic complexity of its description. A cornerstone of this theory is Fagin's Theorem, by which a property is expressible in existential secondorder logic (ESO logic) if, and only if, it is in NP. A natural question, from the theory's point of view, is which syntactic fragments of ESO logic also still characterize NP. Research on this question has culminated in a dichotomy result by Gottlob, Kolaitis, and Schwentick: for each possible quantifier prefix of an ESO formula, the resulting prefix class over graphs either contains an NPcomplete problem or is contained in P. However, the exact complexity of the prefix classes inside P remained elusive. In the present paper, we clear up the picture by showing that for each prefix class of ESO logic, its reduction closure under firstorder reductions is either FO, L, NL, or NP. For undirected selfloopfree graphs two containment results are especially challenging to prove: containment in L for the prefix \exists R_1\cdots \exists R_n \forall x \exists y and containment in FO for the prefix \exists M \forall x \exists y for monadic M. The complex argument by Gottlob et al. concerning polynomial time needs to be carefully reexamined and either combined with the logspace version of Courcelle's Theorem or directly improved to firstorder computations. A different challenge is posed by formulas with the prefix \exists M \forall x\forall y, which we show to express special constraint satisfaction problems that lie in L.
BibTeX  Entry
@InProceedings{tantau:LIPIcs:2015:4952,
author = {Till Tantau},
title = {{Existential Secondorder Logic over Graphs: A Complete Complexitytheoretic Classification}},
booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
pages = {703715},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897781},
ISSN = {18688969},
year = {2015},
volume = {30},
editor = {Ernst W. Mayr and Nicolas Ollinger},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4952},
URN = {urn:nbn:de:0030drops49524},
doi = {10.4230/LIPIcs.STACS.2015.703},
annote = {Keywords: existential secondorder logic, descriptive complexity, logarithmic space}
}
Keywords: 

existential secondorder logic, descriptive complexity, logarithmic space 
Collection: 

32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) 
Issue Date: 

2015 
Date of publication: 

26.02.2015 