2017/04/11 by Yijia Chen, Chen, Yijia, J. Flum +3 · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1704.03167
openalex publication_date 2017/04/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For every q∈ \mathbb N let \textrmFOq denote the class of sentences of first-order logic FO of quantifier rank at most q. If a graph property can be defined in \textrmFOq, then it can be decided in time O(nq). Thus, minimizing q has favorable algorithmic consequences. Many graph properties amount to the existence of a certain set of vertices of size k. Usually this can only be expressed by a sentence of quantifier rank at least k. We use the color-coding method to demonstrate that some (hyper)graph problems can be defined in \textrmFOq where q is independent of k. This property of a graph problem is equivalent to the question of whether the corresponding parameterized problem is in the class \textrmpara-AC0. It is crucial for our results that the FO-sentences have access to built-in addition and multiplication. It is known that then FO corresponds to the circuit complexity class uniform \textrmAC0. We explore the connection between the quantifier rank of FO-sentences and the depth of \textrmAC0-circuits, and prove that \textrmFOq \subsetneq \textrmFOq+1 for structures with built-in addition and multiplication.