Abstract
In 1981, Neil Immerman described a twoplayer game, which he called the "separability game" [Neil Immerman, 1981], that captures the number of quantifiers needed to describe a property in firstorder logic. Immerman’s paper laid the groundwork for studying the number of quantifiers needed to express properties in firstorder logic, but the game seemed to be too complicated to study, and the arguments of the paper almost exclusively used quantifier rank as a lower bound on the total number of quantifiers. However, last year Fagin, Lenchner, Regan and Vyas [Fagin et al., 2021] rediscovered the game, provided some tools for analyzing them, and showed how to utilize them to characterize the number of quantifiers needed to express linear orders of different sizes. In this paper, we push forward in the study of number of quantifiers as a bona fide complexity measure by establishing several new results. First we carefully distinguish minimum number of quantifiers from the more usual descriptive complexity measures, minimum quantifier rank and minimum number of variables. Then, for each positive integer k, we give an explicit example of a property of finite structures (in particular, of finite graphs) that can be expressed with a sentence of quantifier rank k, but where the same property needs 2^Ω(k²) quantifiers to be expressed. We next give the precise number of quantifiers needed to distinguish two rooted trees of different depths. Finally, we give a new upper bound on the number of quantifiers needed to express st connectivity, improving the previous known bound by a constant factor.
BibTeX  Entry
@InProceedings{fagin_et_al:LIPIcs.MFCS.2022.48,
author = {Fagin, Ronald and Lenchner, Jonathan and Vyas, Nikhil and Williams, Ryan},
title = {{On the Number of Quantifiers as a Complexity Measure}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {48:148:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772563},
ISSN = {18688969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16846},
URN = {urn:nbn:de:0030drops168460},
doi = {10.4230/LIPIcs.MFCS.2022.48},
annote = {Keywords: number of quantifiers, multistructural games, complexity measure, st connectivity, trees, rooted trees}
}
Keywords: 

number of quantifiers, multistructural games, complexity measure, st connectivity, trees, rooted trees 
Collection: 

47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) 
Issue Date: 

2022 
Date of publication: 

22.08.2022 