The anaphora problem
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.
computational complexity of human language
scientific article; zbMATH DE number 370448