Complexity of natural language processing problems [closed]

Question

Which natural language processing problems are NP-Complete or NP-Hard?

I've searched the natural-lang-processing and complexity-theory tags (and related complexity tags), but have not turned up any results.

None of the NLP questions that are recommended are helpful, the closest are the following:

• https://cs.stackexchange.com/questions/25925/why-is-natural-language-processing-such-a-difficult-problem

• https://cs.stackexchange.com/questions/9920/how-is-natural-language-processing-related-to-artificial-intelligence

• What aspects of linguistics are necessary or good for natural language processing?

The Wikipedia list of NP-complete problems does not list any complexity results for NLP.

The only lead I've found is the paper Theoretical and Effective Complexity in Natural Language Processing by J. Morin (1995).

Any help or pointers is appreciated!

Answer 1

LFG (Lexical-Functional Grammar) recognition is NP-Complete.

Edit per request: Lexical-Functional Grammar (LFG) [1] is a theory of natural language syntax, developed as an alternative to Chomsky's theories of transformational syntax. Some versions of Chomsky's theories are computationally equivalent to Unrestricted Grammars. LFG by contrast provides a grammar formalism which consists of a context-free grammar augmented by a feature system.

It's the feature system that's NP-complete. The proof works basically by noticing first that the feature system is at least as powerful as propositional logic, and second that grammaticality rests on satisfying all the propositional constraints governing the sentence. So it's the Satisfiability Problem hiding under another guise.

[1] "Lexical-Functional Grammar: A Formal System for Grammatical Representation" by Ronald M Kaplan and Joan Bresnan. The paper originally appeared in The Mental Representation of Grammatical Relations, ed. Joan Bresnan (Cambridge, MA: The MIT Press, 1982).

Answer 2

Maybe one should first define what is a natural language processing (NLP) problem.

For example, Context-Free (CF) grammars and languages were introduced by linguists (Chomsky type 2 language, work of Bar-Hillel and others). Ambiguity is a major problem in Linguistics for real sentence analysis, and in the formal study of CF grammars (ambiguity) and languages (inherent ambiguity). Ambiguity of a grammar is only semi-decidable.

So I guess the problem of ambiguity should be an answer to your question. Does it classify as a NLP problem?

Now if you take some modern formalizations of syntax, such as a CF backbone with feature structures (i.e. structured attributes), you quickly get Turing power (cf LFG which have been proved NP hard, or even Turing complete, depending on variants). So , if you are not careful, you have all the complexity problems you might dream about.

For more, you can also look at this question from SE-Linguistics: "Does the P versus NP conjecture in computer science have any direct relevance to linguistics?"

In my own answer, I actually criticize the meaningfulness of the question, or at least of some of its interpretations. Many of the problems that are considered in linguistics, regarding analysis of sentences, for translation or other purposes, are small problem, to be solved in a very short time. Some linguists might even dispute that there is real recursion in language structure, since whatever recursion there is is rarely very deep. Hence one might wonder about the linguistic relevance of complexity analysis which is defined asymptotically. The first question should be whether we ever get close enough to the asymptote for asymptotic analysis to be meaningful.

However, this remark does not apply to some aspect of NLP, when massive amount of data have to be processed. I know of at least two cases:

• data mining in large corpora.

• the inverse problem of linguistics: analysis of large corpora to mechanically extract the data characterizing a language, both structurally and to produce extensive lists of constituents, such as phonemes, vocabulary for various parts of speech (aka preterminals), prefixes and suffixes, or inflection mechanisms, to give a few examples.

I am no expert in data mining, and thus do not know whether it actually raises complexity problems related to the size of the corpora being processed. In that case, asymptotic complexity would indeed be an issue. But if it is mostly composed of a large number of small additive tasks, then it is more doubtful that asymptotic complexity matters much. However, I would imagine that some data mining techniques will work with correlations between independent documents, and that should raise corpus dependent complexity issues.

In the case of the inverse problem of linguistics, the identification of a language (which, I guess, could be considered a data mining problem), we are indeed trying to extract information by correlating all parts of large corpora. Then asymptotic complexity becomes extremely relevant. I have unfortunately no specific problem in mind, probably because such systems have a pragmatic aim, and people developing them will tend to simply avoid any form of higher complexity, quadratic being probably already beyond the available resources. But a search of the literature would probably raise some complexity issues.

Another point is that linguistics does not have clearcut laws like physics. It is more a matter of being close enough to what might be considered current linguistic consensus, since no two people speak exactly the same language. Hence, good approximations are usually sufficient when the aim is so elusive. The techniques I have seen were mainly fix-point techniques to identify parameters by iterative recomputation of some function based on the corpus structure, until it no longer makes much difference (plus user input to weed out remaining pathological cases).

Analysing properties of grammars and other formalized linguistic structures may also be a source of high complexity problems, as mentioned above for ambiguity, since natural language descriptions are usually large enough for asymptotic analysis to be meaningful.

Answer 3

as in my comment, sometimes P/NP complexity while quite powerful can be a hammer that makes all complexity questions look like nails, and in the field of AI & language translation with statistical, probabilistic, imprecision, and machine learning aspects, it may not be the ideal measurement at times, and theoretical computational complexity is not always considered central or relevant esp in more applied AI/ machine learning. in some ways the entire field has a more empirical aspect to measuring applied problem complexity. however, here is one angle not yet pointed out in other answers, there are some P/NP considerations in NLP language translation. eg these two papers

• Phrase-Based Statistical Machine Translation as a Traveling Salesman Problem / Zaslavskiy, Dymetman, Cancedda

• Computational Complexity of Statistical Machine Translation / Udupa, Magi

  We prove that while IBM Models 1-2 are conceptually and computationally simple, computations involving the higher (and more useful) models are hard. Since it is unlikely that there exists a polynomial time solution for any of these hard problems (unless $P = NP$ and $P^{\#P} = P$), our results highlight and justify the need for developing polynomial time approximations for these computations.