Existential second-order logic over graphs: a complete complexity-theoretic classification

DOI10.4230/LIPICS.STACS.2015.703zbMATH Open1356.68084arXiv1412.6396OpenAlexW2963635167MaRDI QIDQ2955035FDOQ2955035

Authors: Till Tantau 

Publication date: 24 January 2017

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 graph property is expressible in existential second-order 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, Kolatis, and Schwentick: for each possible quantifier prefix of an ESO formula, the resulting prefix class either contains an NP-complete 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 first-order reductions is either FO, L, NL, or NP. For undirected, self-loop-free graphs two containment results are especially challenging to prove: containment in L for the prefix $exists{R}_{1}cdotsexists{R}_{n}forallxexistsy$ and containment in FO for the prefix $existsMforallxexistsy$ for monadic $M$. The complex argument by Gottlob, Kolatis, and Schwentick concerning polynomial time needs to be carefully reexamined and either combined with the logspace version of Courcelle's Theorem or directly improved to first-order computations. A different challenge is posed by formulas with the prefix $existsMforallxforally$: We show that they express special constraint satisfaction problems that lie in L.

Full work available at URL: https://arxiv.org/abs/1412.6396

Recommendations

• Existential second-order logic over graphs: charting the tractability frontier
• Existential second-order logic over strings
• scientific article; zbMATH DE number 1540059
• scientific article; zbMATH DE number 1254648
• The closure of monadic NP

zbMATH Keywords

existential second-order logiclogarithmic spacedescriptive complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (6)

• A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
• Complexity of syntactical tree fragments of independence-friendly logic
• Existential second-order logic over graphs: charting the tractability frontier
• Descriptive complexity of modularity problems on graphs
• Existential second-order logic over strings
• Expressing properties in second- and third-order logic: hypercube graphs and SATQBF

This page was built for publication: Existential second-order logic over graphs: a complete complexity-theoretic classification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2955035)