Quick links

Human Language Comprehension is NP-Complete

Report ID:
May 1991
Download Formats:


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

Follow us: Facebook Twitter Linkedin