The language complexity game
Eric Sven Ristad, Daniel G. Bobrow · 1993
round various aspects of the problem of determining which anaphoric elements in a given sentence can refer to which potential antecedents. Ristad takes the reader through five rounds of what he calls a "complexity game," which is a contest between a maximizer, who tries to make natural languages as complex as possible, and a minimizer, who seeks to reduce the complexity to a bare minimum. In the first round, we read an argument purporting to demonstrate the NPhardness of any language whose anaphora are required to agree in features such as number, gender, and so on with their antecedents. In the second round, this argument is refuted by the minimizer, who claims that the standard theory of how agreement works is wrong and proposes a new theory, under which anaphoric agreement is now recognizable in deterministic polynomial time. In the third turn, a new set of data leads to the central argument in the book, according to which the anaphora problem is NP-hard after all. The facts crucia