2024/02/15 by Carmosino, Marco, Fagin, Ronald, Immerman, Neil +4
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.2402.10293
The number of quantifiers needed to express first-order properties is captured by two-player combinatorial games called multi-structural (MS) games. We play these games on linear orders and strings, and introduce a technique we call "parallel play", that dramatically reduces the number of quantifiers needed in many cases. Linear orders and strings are the most basic representatives of ordered structures -- a class of structures that has historically been notoriously difficult to analyze. Yet, in this paper, we provide upper bounds on the number of quantifiers needed to characterize different-sized subsets of these structures, and prove that they are tight up to constant factors, including, in some cases, up to a factor of 1+ε, for arbitrarily small ε.