Complexity of natural language processing problems
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.