[Solved]: Complexity of natural language processing problems

Problem Detail: 

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:

• Why is natural language processing such a difficult problem?

• 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!

Asked By : yters

Answered By : ShyPerson

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32276