Thursday, July 14, 2011

Why do research?

One day, when I was a student, I asked Andy Yao why he was doing research. As best as I remember, this is what he answered:
-"I need a long-term goal to drive my interest in the field. If the P vs. NP question was resolved tomorrow, I would probably change fields."
I insisted: what did he enjoy the most about doing research?
-"I enjoy the moment right after I have discovered something new. At that time, there is something that I know and that no one else knows yet. It's like being the first person ever to get to the top of a mountain. I spend a few days savoring the feeling."


  1. Usually people who try to discover the famous P versus NP problem say “I have solved it”. For me personally, it seems a bit pretentious to announce such discovery as a fact. I also think it will be difficult for a non-expert in the subject to solve it; this possibility would be like the probability of one in a million. Since 6 years ago I spent my time trying to solve this problem as a hobby and I have found that the model of Turing machines is a great tool to demonstrate that result. I also think, that a trivial way to prove a result in this field is proving that the language sets P and NP are disjoint, demonstrating that there is a problem in NP that is not in P. I upload to Arxiv the version number 11 which although it maybe have trivial mistakes, such as lack of proficiency in English, still remain me convinced since a few months ago. I want someone to refute my arguments, but I am just a lover of the subject outside the academic circuit, I have no one does. Please help me, here is the address:
    (Version 11)

  2. Anonymous, I actually don't work on the P versus NP problem. I only do algorithms, not computational complexity. Sometimes the two sub-areas come close to one another, but I have no competence in computational complexity.

    It seems to me that submitting your work to a journal is the best way to get a serious review. For example JACM, as it is reputedly the top journal, would be more than eager to take a paper that actually solves the P versus NP question.

    However, without knowing anything about your paper, I have to admit to a bit of scepticism. Many proofs have been proposed and all have eventually been shown to have a flaw. I wouldn't be surprised if, like Fermat's last theorem, it was a question that was going to stay open for many generations, inspiring the development of deep techniques that will one day, long after I am dead, answer the question. But maybe you are a genius autodidact - they do exist, Ramanujan for example.

    If this post gave you the impression that Andy Yao was working directly on the P versus NP questrion, I did not mean to say that. In fact I have heard him use the following analogy:

    Imagine you want to go to the moon. There are two ways to go about it. One is to say: "The moon is far up in the sky. I will try to go as close to it as possible. Go up to the top of a mountain and climnb to the top of the highest tree. Then I will be closer to my goal." The other one is to say: "Let me try to understand why it moves in the sky by developing a theory of physics. Let me try to develop some engineering knowledge. I am not sure exactly what that will achieve, but this additional understanding is sure to help in the long run." The first way is misguided, the second way, although it may look haphazard, is ultimately the one that succeeds.

    I think of P versus NP in that way: not as a problem to be attacked directly upfront, but as a distant goal that guides our research in a remote fashion.


Note: Only a member of this blog may post a comment.