Human Language Comprehension is NP-Complete

Abstract:

Consider the computational problem of understanding the utterances of a
human language that contain pronouns. In order to completely
understand such utterances, the language user must determine the
intended reference of each pronoun in a given utterance. For example,
in order to comprehend the english sentence Jocasta loved her son, the
hearer might determine that the possessive pronoun $her$ refers to
Jocasta, the queen of Thebes. We prove that two different models of
this broad computational problem are NP-hard, and argue that the
problem remains in $NP$ even if our language models account for the
computationally complex phenomenon of syntactic ellipsis. These
complexity results are based directly on human linguistic knowledge,
and are invariant across linguistic theories. No knowledge of
linguistic theory is needed to understand the analysis, only knowledge
of English