Computational complexity of syntactic agreement and lexical ambiguity (Q1902598)

What do language users know about particular utterances, and how do they compute this knowledge? These two questions are central to the computational investigation of human language. The defining characteristic of a computation is its complexity -- the amount of time and space that it requires. This article contributes to the computational study of human language by analyzing the complexity of computing the language users' knowledge of syntax. We demonstrate that the process of computing such syntactic knowledge according to modern transformational grammars is NP-hard (that is, as complex as any problem solvable in nondeterministic polynomial time). The results reported here contribute to a larger research program, whose goal is to characterize the complexity of human language. However, unlike prior work on the complexity of natural language, our proof is not based on a complete formalization of a linguistic theory. Instead, we proceed as follows. First, we identify a class of structural descriptions defined by five essential properties. Next, we prove that the language comprehension problem will be NP-hard for any linguistic theory that generates our class of structural descriptions. Finally, we demonstrate that the modern transformational grammars of \textit{H. Lasnick} and \textit{M. Saito} [Ling. Inquiry 15, 235-289 (1984)]\ and \textit{N. Chomsky} [Barriers. (1986)]\ generate this class of structural descriptions and consequently are NP-hard.