Slicewise definability in first-order logic with bounded quantifier rank

Abstract

For every $q\in \mathbb{N}$ let ${\text{FO}}_q$ denote the class of sentences of first-order logic FO of quantifier rank at most $q$. If a graph property can be defined in ${\text{FO}}_q$, then it can be decided in time $O(n^q)$. 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 ${\text{FO}}_q$ 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 ${\text{para-AC}}^0$. 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 ${\text{AC}}^0$. We explore the connection between the quantifier rank of FO-sentences and the depth of ${\text{AC}}^0$-circuits, and prove that ${\text{FO}}_q⊊{\text{FO}}_{q+1}$ for structures with built-in addition and multiplication.