Proceedings of the Annual Meeting of the Cognitive Science Society

Imagine a friend asks: "could you pass me the dragonfruit''. You have no idea what they mean and inquire, "do you mean the orange fruit in the bowl?'', but they respond: "no, the pink one''. Now you know which fruit they want and in future contexts you will likely also understand their request. People seamlessly update beliefs about speakers' (word) meanings. Through interaction they somehow infer what "dragonfruit'' means: are all dragonfruits "pink'', or just this one? Is its shape more diagnostic, or some combination of the two? The number of possible belief updates is vast, growing exponentially with the number of features. Using formal complexity analysis, we prove that state-of-the-art models of communication are computationally intractable. Hence, they cannot yet explain how people can navigate this search space efficiently and communicate seamlessly. The intractability result holds for different model variants, suggesting a fundamental computational challenge for explaining communicative interaction.