Blog moved to Algolife

On Sachin Tendulkar's double century ....

He has never forgotten why he started playing the game in the first place. The best have lofty ambitions when they begin but soon commerce, like a tenacious worm, gnaws into them. Fame surrounds them and prevents the fresh air of reason from breaking through. They acquire sycophants, that great curse of success. Playing the game becomes a means to a seemingly superior but, in reality, a hollower end. Tendulkar has kept those demons at bay. He has made more money than anyone else, acquired greater fame than is imaginable but you could never guess that from the way he plays his cricket. He remains the servant, pursues the game with purity. Through the last decade India have been well served by like minded giants.
And he works as hard as anybody has. Lance Armstrong once said that he wins the Tour de France not when he is cycling down the Champs-Elysees but when he is out in the mountains facing icy winds while others are cozying in their blankets for an extra hour.

Finding Problems to Work On - Prof Lance Fortnow

Often graduate students ask me for a good problem to work on. This is one of the biggest challenges of an advisor. A good problem for a graduate student must fulfill each of three characteristics.
1.Open.
2.Doable.
3.Interesting.

Finding problems that fit any two of these three is not hard, but if a problem is doable and interesting, someone likely would have solved it by now. Too often interesting is the property that is given the least emphasis.
I generally give the advice that my advisor, Michael Sipser, gave to me. Pick up a proceedings of a recent conference in your area and read through the abstracts of papers until you find one that interests you. The "interests you" part is important, for without it you won't have the motivation to study further.

Read the paper thoroughly. Read related papers. If you lose interest, start the process all over again.

Once you've read several papers in an area that interests you talk about it with your advisor and your fellow graduate students. Some of these papers might list open questions and you could work on those. You might say, "Karp listed this as an open question, and if Karp can't solve it why should I be able to?" Karp is a very smart but also very busy person. It is unlikely he spent more than an hour thinking hard about these questions. As a graduate student you can spend much more time focusing on these problems and could easily make more progress than someone like Karp could.

Even better is to formulate your own problems. Perhaps there is an interesting variation in a model that the original paper, for whatever reason, did not cover. Perhaps you can find connections between two papers that no one had noticed before. These are great problems to work on: As you are breaking new ground, theorems can start flowing like water. Just remember not to have too much weirdness in your questions; keep the research interesting.

Only Polynomially bounded algorithm does not suffice.

I have been thinking about my first post for long time. Although I mentioned that predicting the future by pure computation is NP-hard problem, I was not satisfied. Intuitively, the problem is much more harder. And here is the idea how it is.

Since the life is a real time process or it runs in linear time, to know the future in polynomial time is not a sufficient condition. The computation should be done in Linear time Algorithm. As we suspect that P=NP isn't true, it is near to impossible that the NP-hard problem can be solved optimally in polynomial time algorithm. (Again this is a conjecture). And solving a NP-hard problem in a linear time looks more near to impossible. Hence its much harder.