In computer science (especially computational complexity theory), problems can be classified to some complexity theory. For example, we say the travelling salesman problem belongs to NP-complete.

Parsing of a human-language text (e.g. English text) is also a computational problem. Can it be analyzed and classified to some complexity class? If yes, which class does it belong to and why?


While I have been unable to find any excerpts from the book in question, "A Fundamental Algorithm for Dependency Parsing" by M. Covington references "Computational Complexity And Natural Language" by Barton, Berwick, and Ristad, saying:

Barton, Berwick and Ristad... prove that when lexical ambiguity and agreement features are present — that is, when words can be ambiguous and can be labeled with attributes — natural language parsing is NP-complete.

I suspect this book may be of great interest to you.

This conclusion is backed up by "Computational complexity of problems on probabilistic grammars and transducers." by F. Casacuberta et al. which provides proofs that parsing of Stochastic Regular Grammars is NP-Hard as well as "Generation as Dependency Parsing" by A. Koller et al. which offers an ad hoc proof that parsing Topological Dependency Grammars is also NP-complete. As well as several other papers I found with a quick search on Google Scholar.

  • The reason is that parsing per se -- i.e, only syntactic parsing -- produces multiple ambiguities that are usually resolved in practice by semantic, pragmatic, metaphorical, or local personal conventions. I.e, statistics.
    – jlawler
    Apr 30 '13 at 18:45
  • The paper by Berwick is at www.aclweb.org/anthology-new/J/J82/J82-3001.pdf, in case you want to update your link.
    – prash
    May 2 '13 at 22:51
  • This is not a criticism of what you wrote, but Berwick ends his paper in an uncertain tone. (I have only skimmed it, so I might be wrong.) But papers that cite this seem to make it sound like Berwick established a proof.
    – prash
    May 2 '13 at 22:58
  • @prash The paper I'm quote is actually citing a textbook, not the paper you link. Perhaps the textbook contains an actual proof? I suspect that there are too many variations across languages to say in a general case whether parsing natural languages is in any complexity class. But the original question sparked my interest and this answer is just a collection of the papers I found helpful.
    – acattle
    May 3 '13 at 1:21
  • @prash From what I read, this Berwick's paper only shows that LFG is NP-hard. It seems that there is a later proof that it is NP-complete.
    – babou
    Dec 13 '13 at 16:43

It depends on the framework. Within LFG, parsing is NP-compete in the worst case. However, Ron Kaplan argues that NL parsing is polynomial in the average case. In general, NL parsing is NP-complete because of the constraints associated with rules.

  • As you said, parsing complexity depends on the framework. Some frameworks can be very powerful, beyond NP-completeness, though that is bad enough. For many years it was known that LFG were NP-hard, and it took some time to prove that its complexity is limited to NP-completeness.
    – babou
    Dec 13 '13 at 16:32
  • @babou Do you know who proved it? LFG parsing can be translated into SAT but I guess the original proof was different.
    – Atamiri
    Mar 5 '15 at 0:59
  • I think the reference is easily found on the web. There ar several of them. But I do not remember off hand. I was traveling for a while, hence late answer. If you do not find it ask again, I will look. ai.ato.ms/MITECS/Entry/dalrymple.html => It has been shown that LFG recognition is NP-complete (Berwick 1982) : Berwick, R. (1982). Computational complexity and Lexical Functional Grammar. American Journal of Computational Linguistics 8:97-109.
    – babou
    Mar 5 '15 at 20:39
  • Maybe look at: download\?doi\=\&rep\=rep1\&type\=pdf Unification-based grammars and complexity classes, Anders Søgaard
    – babou
    Mar 5 '15 at 20:53
  • @babou Thanks, the references in Søgaard's paper are very helpful.
    – Atamiri
    Mar 5 '15 at 21:00

Preliminary note: I tried to be as general as possible, but the variety of syntactic descriptions of Natural Language is such that it is unlikely that everyone will find here his preferred brand of syntax or parsing. For example, the parsing of lexicalized descriptions of language is not directly accounted for. I am not sure that this can be helped in any reasonnable way. My purpose here has been mainly to explore the range of questions that could or should be addressed when considering the complexity of natural language parsing.

The first point is that "Parsing of a human-language text" is an ill defined task. Complexity analysis is a mathematical endeavor which makes sense only within a mathematically well defined framework. You can therefore ask such a question only with respect to a given formal description of the language syntax.

Another preliminary point is that parsing is supposed to analyze syntax only, not semantics. But where is the border between syntax and semantics.

What is parsing ?

Parsing is always done with respect to a grammar (term used loosely to mean a description of the syntax) of a language in some appropriate formalism (formal framework). So the complexity classes are also classifying these formalisms.

Secondly, the concept of parsing itself should be precisely defined, It is clear that it is an algorithm taking as input a sentence (meaning only a linear sequence of words) and produces as output a structure that give a more explicit description of the sentence emphisizing the structural properties that make it belong to the language specified by the given grammar (I am trying very hard not to be too specific).

For example, with a generative grammar, the output of the parsing process may be a structure that describes precisely how the sentence can be generated by that grammar, when it is syntactically correct, i.e. when it belongs to the language described.

Furthermore, it is known that natural languages are generally syntactically ambiguous, i.e., that some syntactically correct sentences can be structurally described in several ways (generated in differents ways). Note that a sentence can be syntactically ambiguous, even though there is no semantic ambuiguity. Now the result expected from parsing could be :

  • just be a yes/no answer stating whether the sentence is syntactically correct. This is usually called recognition, rather than parsing;
  • any of the possible structural descriptions of the input sentence; when it is syntactically correct.
  • all the structural descriptions of the input sentence; when it is syntactically correct. This itself opens a spectrum of possibilities as there may be different ways of representing this (possibly infinite) set of parses, which may be more space efficient or easier to use for later stages of the sentence analysis. See for example the question Is there a favoured data structure for storing ambiguous parse trees in Natural Language Processing? ;
  • one or more structural descriptions of the input sentence, when it is syntactically correct, satisfying some preference or selection criterion.

In addition, the nature of the expected structural description may vary. Typically, the result of parsing a sentence according to a tree adjoining grammar (TAG) can be a (set of) derivation(s) tree(s) or a (set of) derived tree(s). Derivation trees and derived trees are distinct for TAG.

It is not obvious that the complexity is the same for all choices of what is expected as parsing result for a given formalism.

What is complexity ?

If the formalisms, and the result expected from the parsing process, are properly defined, it is of course possible to classify the parsing process for that formalism of in some complexity class, or more precisely to do a complexity analysis of the parsing process, as complexity classes come in many flavors : time complexity or space complexity, asymptotic worst case complexity or average complexity.

Though people often think of asymptotic worst case time complexity, it may make more sense in practice to consider average complexity. So such clssifications into complexity classes should be interpreted with care from a pragmatic point of view.

Another point is that complexity is often considered with respect to the size (number of words) of the sentence to be parsed. But complexity may also be analyzed with respect to the size of the grammar used to analyze a sentence. This is important as some people tend to increase the size of the syntax description in order to capture rarer or more subtle phenomena. This does not come for free.

Many formalisms are composed of a formal generative skeleton (such as context-free grammars) where various attributes (features, probabilities, ...) can be associated to the rules constituents, having to respect various constraints associated to the rule. The addition of these attributes and the respect of these constraints increases, often drastically, the complexity of the formalism, making it NP-hard, and even possibly Turing-complete (allowing you to encode as a parsing problem any algorithm you can dream of).

Of course there are zillions of subcases providing interesting complexity problems to people inclined to such studies.

One aspect commonly analyzed is the complexity of skeleton formalisms, without any attribute. Typically parsing context-free languages has time complexity O(n³), which is fairly low and quite tractable in practice. However, some structural organizations of the sentences cannot be captured by CF grammar. A classical example is cross-serial dependency.

Rather than add attributes to somehow encode the information necessary to handle such structures in a very general feature mechanism, some scientists consider that it is more effective, and possibly more perspicuous, to complexify a bit the skeleton formalism. This for example lead to the development of Tree Adjoining Grammars (time complexity O(n⁶)), then to a hierarchy of formalisms with increasing polynomial complexity, and the so-called mildly context-sensitive formalisms and Linear Context-Free rewriting systems. One remarkable aspect is that, though the polynomial worst-case complexity may seem high, structures producing high complexity may be few, so that things remain very tractable in practice.

This is to underscore, again, that complexity analysis does not necessarily tell the whole story.

Your Answer

