Who has time to do the research?

by JS

… or how important is that problem really?

There’s an interesting attempt to prove P \ne NP floating around. The best set of initial reactions seems to be here. Beyond the absolute basics, I can’t evaluate what’s going on with the proof, and anyway it seems like most of AI is predicated on the assumption that P \ne NP so we really only have to worry about our basic assumptions regarding complexity if a serious paper comes along proving the opposite.

[Aside: I'm being a bit glib about this important problem. For one thing, their are some interesting implications for various lower bounds on the class NP that might be of immediate practical concern in AI. But on the other hand there's also something of a category distinction between worrying about problem difficulty in strictly computational terms and fighting with the finicky nature of a robot arm that won't grasp a damn block. Another way to think of the distinction is that object recognition in humans is very nearly instantaneous and probably computed using some kind of constant depth circuit. But we're not even close to finding even a much slower algorithm that can do the same thing at nearly the level of an average adult.]

There are a couple of interesting issues with exactly how this paper came to be so public. First, it seems like the author sent it to a small number of people looking for some feedback. With a result of this kind, you’d probably want to be cautious with your handling of the draft before even uploading a copy to arXiv. That caution didn’t really pan out in this era of social networking. Now the researcher is stuck defending a non-publication that he just wanted a second opinion on as if it were a final manuscript. I bet that’s sort of awkward. Then again, it already looks like this probably incorrect proof brings some new ideas to the table, so reputation-wise this may be a net positive for the researcher involved.

Also, it seems like there was some hesitation on the part of complexity theorists to even begin to evaluate the proof. This is not really odd considering the number of “proofs” that arise for all kinds of famous open problems. That said, one aspect of the hesitance seems to be that nobody really works on proving P \ne NP anymore. The demands of research (and research funding) push people in research positions at research universities away from anything that can’t yield some form of paper every six months. The general attitude is that proposals that focus on proving P \ne NP do not get funded and so nobody works on the problem (or pays students to do so) with anything like their full attention. Supposing this particular paper is the real deal, it serves as something of an indictment of the university establishment that eschews working on big picture problems and instead focuses on what can be published in the next six page double column conference paper. In any event, the fact a dedicated researcher with the necessary background can put forward a compelling effort in his spare time must say something about the way full time complexity theorists allocate their resources.

Just saying.

UPDATE: Actually, this isn’t even really an indictment. I’m not even sure the fact that so much focus is placed on rapid fire results in conferences is a bad thing. I guess the point I’m trying to make is that when evaluated sociologically, P \ne NP is not actually an important problem at all. That is to say it is far less important in practical terms than the latest and greatest ad auction theory proposal that actually does get funded and gets the care and attention of many seasoned researchers.