Hacker News Reader

Comment by yters | Hacker News Reader

If p != np, then comp sci will lose much of its appeal. There is an underlying hope behind the field that p = np, otherwise most problems of interest are intractable, and programmers are no longer masters of the universe.

This is probably why there is not a proof yet, since the truth is undesirable.

View on HN

I'm not sure what you mean by "appeal." But, it seems to me that if P = NP, and if we can find a constructive proof of this fact, i.e. someone presents a P-time algorithm A_L deciding an NP-complete language L, the field of CS in a sense would get much less interesting, because although we would have answered arguably the most important question ever posed, there would be much less of a need to research and develop efficient algorithms or approximation strategies. We'd probably just focus on trying to improve the runtime of A_L and the reductions from other NP languages.

Yes every field is of interest to its specialists. But the popular appeal is that comp sci promises the ultimate explanation of a materialistic reality. At least this was its appeal when I chose it for my major, and it drives the religious transhumanism and the AI hype and arguably the funding of IT. But if the public learns seemingly trivial problems are inherently intractable or impossible for computers, that glamorous spectacle will shatter.

> If p != np, then comp sci will lose much of its appeal.

Say what? A lot of work is based on the assumption that P!=NP so you have to be clever in other ways.

All that work is boring to the non specialist. It's the promise of unlimited power that gives IT glamor.

That's like saying Math will lose its appeal because there is no algorithm to find prime numbers.

P != NP is natural, you just gotta roll with it.

There is an algorithm to find prime numbers. It might not be efficient but it exists.

Uh... P ISN'T known to equal NP, but people seem to have a lot of fun using computers anyway.

Arguably, P=NP makes CS less fun, since an efficient "universal algorithm" could solve a vast class of problems in polynomial time, while P != NP means there's more room for programmer creativity making intractable problems tractable in special cases.

No, all of cryptography is based on the assumption that P !=NP

  This is probably why there is not a proof yet, since the truth is undesirable.

You are presenting an explanation to a false observation.

Reply on news.ycombinator.com