“The P versus NP problem is a major unsolved problem in computer science. Informally, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.” - Wikipedia

What I'm asking is whether there is any concept or project of a decidedly linguistic nature that would make you think, "Hey, that reminds me of the P versus NP conjecture in computer science," supposing that you are already familiar with said conjecture.

  • I am wondering what is the exact meaning of your question. Are you interested in all formal linguistics problems that happen to be NP-complete when considered as abstract mathematical/computational issues ? There are hundreds of such problems in the literature (e.g., in formal languages theory). Or are you interested only in such problems when the NP-completeness issue is linguistically relevant ? I would think these are much harder to evidence, and it is very doubtful that any can be found related to psycho-physio-linguistics as suggested in some answers. – babou Dec 2 '13 at 11:49

I think that Xophmeister's answer is pretty good. I wanted to chime in with the paper he or she was searching for, and since I don't have enough reputation to comment, I had to post an answer.

In general, I would not exactly say that the P-NP problem is causing theoretical linguists to lose sleep. However, contingent on the conjecture that P does not equal NP, there is a problem for Optimality Theory. Idsardi (2005) proves that the problem of generating an "intermediate candidate set" in OT is NP-hard. Thus, by conjecture, the flavor of OT examined by Idsardi is computationally intractable.

As suggested by Xophmeister, theoretical computational linguists are interested in complexity in general.


Idsardi, William J. (2006) A Simple Proof that Optimality Theory is Computationally Intractable. Linguistic Inquiry 37: 271-275. link

| improve this answer | |
  • +1 for the reference, @Tanner :) It's reassuring to know that my memory isn't failing me! – Xophmeister Nov 26 '13 at 8:45
  • @Xophmeister - As I explain in my answer below, I doubt that complexity analysis and NP-hardness is very relevant to psycho linguistics, though I am no expert on this. Complexity analysis in general, and NP-hardness in particular, analyses asymptotic situation when the size of the problem becomes very large. But our brain is usually limited to smallish problems. So a psycho-linguistic argument should be much more concerned with the complexity of structures needed to process small problems. – babou Nov 30 '13 at 17:50

There is a notion of computational complexity in generative linguistics when, say, one is trying to justify a theory/framework by considering its physio/psychological plausibility.

That is: If one considers a human brain (and therefore the linguistic processing centres, thereof) as a hyper-parallelised computer, any theory that appears to blow up with an NP solution can be seen as less likely, or even ruled out. Our hardware -- any hardware -- can't support it.

I don't have direct references off the top of my head, but I believe this is an argument against Optimality Theory. The solution space is so vast that it quickly becomes untenable to process and, therefore, unlikely that this is actually how our brains work.

| improve this answer | |

It's much harder to show that it's not relevant to any branch of linguistics than to show that there is at least one application of the P-NP problem in linguistics. But I haven't heard of any.

It's probably obvious why it is not relevant to branches of linguistics that don't have any computational component, such as historical linguistics. But other, rather more computational branches, of linguistics also seem to have a lot of other problems to care about. In corpus linguistics, important questions are

  • How can I speed up the process of compiling a corpus, for example transcription of spoken material?
  • How can I ensure my corpus is a representative sample of the language at hand?

In computational linguistics, interesting questions might concern how parsers or taggers can be improved. If we compare their performance to that of humans, automatic parsers and taggers still have quite some way to go. But the way to improve them is probably not to reduce computational complexity because what computers currently lack and humans have is not more computational power, but real world knowledge.

Take for example:

Yesterday I shot an elephant in my pajamas. How he got into my pajamas I don't know.

You probably parsed this initially with the prepositional phrase "in my pajamas" attached to the verb phrase, as an adverbial. And that's the only sensible reading of this sentence. Initially, you would not even consider (consciously) that "in my pajamas" could attach to "an elephant" because this does not agree with your knowledge of what elephants do. Only the second sentence makes that plausible.

An automatic parser doesn't have real world knowledge at its disposal, and can't exclude the reading "elephant wearing pajamas" right away as non-sensical. Technically, there is not a single correct parse of this sentence, but multiple. Only ranking the different parses and their meanings by likelihood solves the problem.

The challenge is to get this knowledge into parsers. But then we would actually need a computer program that understands human language.

So, in essence I believe the P-NP problem is quite irrelvant to linguistics. But I'm looking forward to any examples showing the opposite :)

| improve this answer | |
  • A parser can easily take all possible attachments into account and leave it to a later stage of sentence analysis to determine which is the right one. If you are trying to understand the semantics, you do need world knowledge. Also true if your processing depends on semantics. But typically you can do some machine translation without ever having to resolve the ambiguity. Attachment ambiguity is exponential, though it matters little. But proper structure sharing can do away with the exponential. – babou Nov 30 '13 at 17:37

Yes, there is. I am referring to the Stanford project " QUANTITATIVE FORMALISM: AN EXPERIMENT":

"This paper is the report of a study conducted by five people – four at Stanford, and one at the University of Wisconsin – which tried to establish whether computer-generated algorithms could “recognize” literary genres."

Here is the link:


I am given to understand that most people familiar with the conjecture conjecture that it is false, that is, creating a work of art is orders of magnitude more difficult than appreciating/recognizing a work of art, and I certainly concur in conjecturing that the conjecture is false. This Stanford project would certainly support this position. If a computer, under present-day technology, can distinguish between genres, I think we would all agree that we are still ages away from the day that a computer can CREATE a worthy work in any genre.

In the news recently it has been reported that baboons can distinguish words from non-words.

Here is the link to the news story:


Your question, then, can be considered as a special case of the more general question that can be catchily-phrased as, "Can baboons do linguistics?"

This conjures up the image of the proverbial room full of monkeys (/baboons) randomly pecking away at typewriters. Will they every produce, say, Hamlet? Of, course, given enough time. But that is consistent with conjecturing that the conjecture is false, because although they (or, an algorithm) may be able to recognize literary phenomena in polynomial time, it would, presumably, take much more than polynomial time to CREATE a literary phenomenon.

"I am at one with my duality." --Woody Allen

| improve this answer | |

What I'm asking is whether there is any concept or project of a decidedly linguistic nature that would make you think, "Hey, that reminds me of the P versus NP conjecture in computer science," supposing that you are already familiar with said conjecture.

Sure. Take a look at essentially any article by Thomas Graf for instance.

Research page of Thomas Graf

| improve this answer | |

I guess many mathematical formalizations of linguistic issues can lead to complexity analysis, and possibly to NP-hard problem. Usually it does not matter too much because we are dealing with small problem. Even if a sentence is long, the complex parts of its structure are likely to be local to a smaller identifiable subpart. Complexity is often mathematically interesting, but linguistically irrelevant. Furthermore, there are often ways to encode cheaply with proper structures situation that would lead to combinatorial explosion (simple example: long prepositional attachment). Shared forests can do that in parsing.

To take an example from computer science. The typing algorithm for the language ML has a double exponential complexity. Pretty bad, except for the fact that the pathological situations are never encountered in practice, and the language has been in use for more than 30 years. Note that even in this bad case, structure sharing techniques can do away with one of the two exponentials (as long as you do not try to print results). There are other examples of the non relevance of complexity analysis.

Now, does this mean that computational linguistics should not worry about complexity and NP-hardeness. I would think these are more likely to crop up when doing complex corpus processing to extract linguistic information about a language. Corpora are usually large, so that anything exponential will be a real problem. My experience there is limited, and the techniques I used did not raise that kind of issue, as I recall, but this is definitely the area of computational linguistics where I would worry about such issues.

I personnally do not think the topic is very relevant to psycho-linguistics, because our brain is swamped by complexity much before we reach exponential complexity. High polynomial complexity is often beyond our ability. But then, I am not a psycho-linguist and I read few papers about it. They were concerned with sructural complexity of small examples, not with asymptotic complexity of large example, which is what P=NP is about.

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.