5 ms·
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 intra
by yters 9y ago
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.
- assface 9y ago> 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.
- yters 9y agoAll that work is boring to the non specialist. It's the promise of unlimited power that gives IT glamor.
- Ar-Curunir 9y agoNo, all of cryptography is based on the assumption that P !=NP
- azdavis 9y agoI'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.
- yters 9y agoYes 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.
- DSrcl 9y agoThis is probably why there is not a proof yet, since the truth is undesirable. You are presenting an explanation to a false observation.
- legohead 9y agoThat'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.
- bigleagueposter 9y agoThere is an algorithm to find prime numbers. It might not be efficient but it exists.
- dubstepjuggalo 9y agoUh... 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.