Loading ...
Sorry, an error occurred while loading the content.
 

[My Computational Complexity Web Log] RESULTAPHOBIA!

Expand Messages
  • Lance
    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
    Message 1 of 1 , Jul 7, 2004
      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 apocraphyl 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@... and postow@....

      --
      Posted by Lance to My Computational Complexity Web Log at 7/7/2004 10:59:04 PM

    Your message has been successfully submitted and would be delivered to recipients shortly.