From Wikipedia:
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.
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 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.
References:
Idsardi, William J. (2006) A Simple Proof that Optimality Theory is Computationally Intractable. Linguistic Inquiry 37: 271-275. link
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.
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
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 :)
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:
http://litlab.stanford.edu/?page_id=255
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:
http://en-maktoob.news.yahoo.com/dan-dan-baboon-read-dan-read-181901087.html
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
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.
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.
