Hacker News new | past | comments | ask | show | jobs | submit login

The last paragraph of the article was inspiring. What you say in (2) is nonsense.

Look at it this way: there are lots of examples when someone sought out to solve one problem and ended up solving another or discovering a new problem -- of which is orthogonal to the original problem.

The author was just conveying the field of complexity has grown tremendously from the nature of this problem being so intractable. See Prof. Papadimitriou et al book Combinatorial Complexity as one example that I'm familiar with.

ASIDE: Also for me, I find the discovery of new problems more exhilarating than the solving established problems via new techniques.




What I said in (2) is not nonsense but actually important in the 'sociology' of that field of research: There are people in the field very much hoping that P versus NP will not be resolved so that they can have long lasting jobs, and you would be naive about people and their tactics to say this is "nonsense".

You seem to be forgetting my introduction that I agree that the question of P versus NP is important. The question is good research, and your point is one reason it is.

Note: Although in computing your use of 'orthogonal' is common, a better word choice would be 'independent' or just 'unrelated'.

For you I will try to be still more clear: When I started working on airline scheduling, I talked to a famous mathematician and explained my airline fleet scheduling problem. Right away he said: "NP-complete" and then dismissed my work as hopeless. He was wrong, badly wrong. Airline fleet scheduling can work quite well in practice, thank you. His blurting out "NP-complete" was just a way to dismiss practical problem solving.

For some good public information on airline fleet scheduling, see the work of Ellis Johnson, then at IBM's Yorktown Heights lab, using IBM's Optimization Subroutine Library (OSL), for American Airlines. Ellis understands NP-complete just fine, but he also knows that it's possible in practice to do quite well on the NP-complete problems of real airlines.

Again, our goals in practice do not have to wait for P versus NP. Read again what I wrote about the cartoon.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: