A Dichotomy Result for Ramsey Quantifiers?

Abstract. Ramsey quantifiers are a natural object of study not only for logic and computer science, but also for formal semantics of natu-ral language. Restricting attention to finite models leads to the natural question whether all Ramsey quantifiers are either polynomial-time com-putable or NP-hard, and whether we can give a natural characterization of the polynomial-time computable quantifiers. In this paper, we first show that there exist intermediate Ramsey quantifiers and then we prove a dichotomy result for a large and natural class of Ramsey quantifiers, based on a reasonable and widely-believed complexity assumption. We show that the polynomial-time computable quantifiers in this class are exactly the constant-log-bounded Ramsey quantifiers.