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

P = NP would touch almost every field known to man: maths (e.g. it would only be matter of search to take down the remaining Clay Problems), philosophy, engineering, biology, physics.

The tie to physics is particularly interesting: for example if Quantum mechanics was a nonlinear theory then we could physically solve NP complete problems [1]. Note the implication, this is not to say p = np => QM nonlinear. The utopian consequences of p = np are discussed very engagingly by Scott Aaronson here [2].

I suggest you also check out his blog as well - his writing style is clear and fun. Plus there was a recent discussion there that linked complexity theory to foundational physics.

[1] http://arxiv.org/abs/quant-ph/9801041

[2] http://www.scottaaronson.com/papers/npcomplete.pdf




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

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

Search: