Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25)

Abstract: For every

q i n m a t h b b N

let

e x t r m {F O}_{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

e x t r m {F O}_{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

e x t r m {F O}_{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

e x t r m {p a r a - A C}^{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

e x t r m {A C}^{0}

. We explore the connection between the quantifier rank of FO-sentences and the depth of

e x t r m {A C}^{0}

-circuits, and prove that

e x t r m {F O}_{q} s u b s e t n e q e x t r m {F O}_{q + 1}

for structures with built-in addition and multiplication.

Recommendations

Cited in

(11)

This page was built for publication: Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.

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