Computational consequences of agreement and ambiguity in natural language (Q1812775)

It is proved that parsing natural languages may be ``computationally intractable''; more exactly, NP-hard. This is done by transforming the satisfiability problem of propositional logic into the parsing problem. The paper is well written and nice to read. However, one should not draw too strong conclusions from a result like this. When parsing natural languages, the problem instances (sentences) are usually quite small and hence an asymptotic complexity function is not very useful.