Bringmann, Karl ;
Fischer, Nick ;
Künnemann, Marvin
A FineGrained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^kForallQuantified FirstOrder Graph Properties
Abstract
An important class of problems in logics and database theory is given by fixing a firstorder property psi over a relational structure, and considering the modelchecking problem for psi. Recently, Gao, Impagliazzo, Kolokolova, and Williams (SODA 2017) identified this class as fundamental for the theory of finegrained complexity in P, by showing that the (Sparse) Orthogonal Vectors problem is complete for this class under finegrained reductions. This raises the question whether finegrained complexity can yield a precise understanding of all firstorder modelchecking problems. Specifically, can we determine, for any fixed firstorder property psi, the exponent of the optimal running time O(m^{c_psi}), where m denotes the number of tuples in the relational structure?
Towards answering this question, in this work we give a dichotomy for the class of exists^kforallquantified graph properties. For every such property psi, we either give a polynomialtime improvement over the baseline O(m^k)time algorithm or show that it requires time m^{ko(1)} under the hypothesis that MAX3SAT has no O((2epsilon)^n)time algorithm. More precisely, we define a hardness parameter h = H(psi) such that psi can be decided in time O(m^{kepsilon}) if h <=2 and requires time m^{ko(1)} for h >= 3 unless the huniform HyperClique hypothesis fails. This unveils a natural hardness hierarchy within firstorder properties: for any h >= 3, we show that there exists a exists^kforallquantified graph property psi with hardness H(psi)=h that is solvable in time O(m^{kepsilon}) if and only if the huniform HyperClique hypothesis fails. Finally, we give more precise upper and lower bounds for an exemplary class of formulas with k=3 and extend our classification to a counting dichotomy.
BibTeX  Entry
@InProceedings{bringmann_et_al:LIPIcs:2019:10853,
author = {Karl Bringmann and Nick Fischer and Marvin K{\"u}nnemann},
title = {{A FineGrained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^kForallQuantified FirstOrder Graph Properties}},
booktitle = {34th Computational Complexity Conference (CCC 2019)},
pages = {31:131:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771160},
ISSN = {18688969},
year = {2019},
volume = {137},
editor = {Amir Shpilka},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10853},
URN = {urn:nbn:de:0030drops108533},
doi = {10.4230/LIPIcs.CCC.2019.31},
annote = {Keywords: Finegrained Complexity, Hardness in P, Hyperclique Conjecture, Constrained Triangle Detection}
}
2019
Keywords: 

Finegrained Complexity, Hardness in P, Hyperclique Conjecture, Constrained Triangle Detection 
Seminar: 

34th Computational Complexity Conference (CCC 2019)

Issue date: 

2019 
Date of publication: 

2019 