On the Number of Quantifiers as a Complexity Measure

Ronald Fagin, Jonathan Lenchner, Nikhil Vyas +1

In 1981, Neil Immerman described a two-player game, which he called the "separability game" \cite{Immerman81}, that captures the number of quantifiers needed to describe a property…