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

But assuming P!=NP, it's resolution will probably have very little impact on the world.



That's (again, probably) not true, although none of the recent flurry of blog posts have explained why not (possibly because it's hard to make this convincing if you're not familiar with mathematical research).

The point is that solutions to such problems as this do not exist in a vacuum: even with the million-dollar incentive for solving the particular stated problems we do not expect that they will be solved without building a network of related sub-theories and sub-theorems, reusable tools which will also help with solving future problems which we don't yet even know enough to formulate.

Fermat's Last Theorem was a good example of this: nobody cares about sums of nth powers, but everybody cares about the Mordell conjecture, Taniyama–Shimura–Weil conjecture etc. which were proved along the way. FLT itself is just a line in the sand to illustrate how far we've come since 1637.


Is it likely that a proof of P!=NP will give insight into designing more efficient algorithms? Or mostly insight into proving other lower bounds?


Perhaps we could get new upper bounds out of it. Or---perhaps the eventual proof will establish a link between hitherto unrelated areas of mathematics. This link could be used to transform whole classes of theorems and proof structures / ideas from one field to another.


I think his argument is that such a proof would represent a significant advance in human knowledge. At its time of origin, the special theory of relativity didn't give anyone nicer cars, either.


I agree, except that it would free up brainpower to work on other problems, and that it would allow more confidence in cryptosystems that rely on an NP-hard problem being exponential time (but I don't think factoring a large product of two primes like could break RSA, is NP-hard).

A resolution P=NP would likely have a huge practical effect, but most people don't expect that to happen.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

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

Search: