The anaphora problem (Q1260651)

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 references of each pronoun in a given utterances. For example, in order to comprehend the English sentence ``Jocasta loved her son'', the hearer might determine that the possessive pronoun ``her'' and the proper noun ``Jocasta'' both refer to Jocasta, the Queen of Thebes. Using such facts of linguistic knowledge, we develop a sophisticated formal model of this computational problem and prove that it is NP-complete. This result is the first empirically-plausible bound on the computational complexity of human language. No knowledge of linguistic theory is needed to understand our analysis, only knowledge of English.