In the 1970's there was some hope that deep techniques from Computability theory might crack P vs NP. Some nice results came out of this (e.g., Ladner's theorem that if P ≠ NP then there is a set inbetween). Then the oracle results seemed to say these techniques (whatever that means) would not work.
In the 1980's there was some hope that deep techniques from Combinatorics might crack P vs NP. Some nice results came out of this (e.g., PARITY not in AC0, and the monotone circuits lower bounds). Then the Natural Proofs framework seemed to say these techniques (whatever that means) would not work.
So where are we now? Fortnow and Homer's paper on the History of Complexity Theory seems to say that we have no ideas at this time. A recent talk at Complexity seemed to say "we didn't work on this aspect of the problem since, if we solved it, we would have P ≠ NP."
We as a community seemed to be afraid of big separation results. We are almost scared of working on hard problems since they might not pan out. Is this wise? There are stories (some apocryphal some not) about people solving problems because they didn't know they were hard. (Examples below)
I recognize that working on problems with little hope of success is dangerous. But to shy away from a line of research BECAUSE it may lead to a big result seems... odd.
EXAMPLE ONE: Neil Immerman tells a story about Robert Szelepcsényi. Szelepcsényi's result that Context Sensitive Languages are closed under complement was announced in an issue of EATCS (in the same issue, two other articles mentioned Immerman's own proof that NSPACE is closed under complement, an effectively equivalent result). Szelepcsényi was an undergrad at the time, and his adviser gave him the famous problem as a challenge, probably not really expecting him to actually solve it. He did solve it, perhaps because he was never told that it was an old open problem that others had failed to solve.
EXAMPLE TWO: A prominent researcher (who told me about this, so its verified) was working on Σ2-SPACE(n) = Π2SPACE(n) but stopped since it might lead to the absurd result that Σ1-SPACE(n)=Π1=SPACE(n).
DEBUNKING: There is a RUMOR that Umesh Vazarani would have had Quantum factoring in P but didn't get it since it was obviously false. He has denied this. (I put this in so that someone doesn't post a comment about it.)
Are there more cases of either people solving a problem because they didn't know it was open OR of people NOT working on a problem because they thought it was hard (and it wasn't that hard)? I'm sure there there are. If you know of any that have been verified please post to comments or email to gasarch@cs.umd.edu and postow@acm.org.
Sorry for anonymous post, A famous example is Huffman code, once I read an interview with huffman, seemingly he has been an undergrad student in a course taught by Shannon. Shannon says in the class that whoever finds the optimum code would receive full mark in the course (or another great prize) but he didn't mentioned that the problem is open. Huffman solved it and won the prize!
ReplyDeleteIt's great to read stories like this, because there are urban legends floating around about the very same theme: A student comes to class late and writes down 10 problems from the board, believing it was homework. The student turns in solutions for a fair number of problems, not knowing the list was open problems in the field. Either way, it's a great story.
ReplyDeleteIt makes me think back to an Alan Kay quote where the work at PARC on Smalltalk is described as nothing short of amazing and Kay replied "we didn't know it was hard."
I have a question, the text notes "the absurd result that ?1-SPACE(n)=?1=SPACE(n)." Am I to assume that the implication is that the "absurd result" is actually true? I am not aware of the class ?1-SPACE(n). Thanks. :-)
ReplyDelete