Human Language Comprehension is NP-Complete
Report ID: TR-337-91Author: Ristad, Eric Sven
Date: 1991-06-00
Pages: 43
Download Formats: |PDF|
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