Complexity of Quantified Reciprocals

This chapter is concerned with the linguistic case study. I investigate the computational complexity of different interpretations of reciprocal expressions, like ‘each other’ in English. I show that Ramsey quantifiers express the semantics of reciprocal sentences with a quantifier in the antecedent. As a result I find a computational dichotomy between different interpretations of reciprocals: some of them are tractable when others are intractable. This dichotomy is consistent with well-known semantic distinctions among different interpretations of ‘each other’. I discuss the impact of this dichotomy on the so-called Strong Meaning Hypothesis proposed as a pragmatic explanation for shifts occurring among different reciprocal readings. I argue that shifts between different interpretations of reciprocal sentences, predicted by the Strong Meaning Hypothesis, can be caused by differences in computational complexity between various readings of reciprocity. I overview psychological evidence s...