Complexity of Polyadic Quantifiers

In this chapter, rather mathematical in nature, I provide a top-down computational perspective on polyadic quantification in natural language, that is, starting with a general computational model of Turing machines I investigate complexity differences between various polyadic constructions. I propose a classification of natural language polyadic quantifiers with respect to their computational complexity, especially focusing on the border between tractable and intractable constructions. First, I prove that iteration, cumulation, and resumption do not carry us outside polynomial computability. Other polyadic construction, like branching and Ramseyification, can lead to NP-complete natural language constructions. In the last section of this chapter-motivated by the search for noncontroversial intractable semantic constructions-I investigate the computational complexity duality between Ramsey quantifiers: some are in P while others are NP-complete. Ramsey quantifiers are a natural object o...