A Guest Post by Bill Gasarch and Brian Postow
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.