News for hackers. Stuff that matters.

A comment on P = NP. Parent comment

Re:P = NP by dllthomas on Wednesday December 04, 2013 @11:36AM (#6848005)
Say we find an algorithm to solve SAT in O(x^1000). P would equal NP, and yet the set of problems we currently label NP-complete might still be substantially harder to solve than to verify.
[ Parent | on HN ]
Re:P = NP by mion on Wednesday December 04, 2013 @12:27PM (#6848445)
Thus rendering the theory rather "useless". What some people are trying to do by attempting to prove N = NP (and this is the main source of criticism), is to find a way to "hack" nature.
[ Parent | on HN ]
Re:P = NP by dllthomas on Wednesday December 04, 2013 @12:59PM (#6848725)
Theory often proves fruitful in unexpected ways.
[ Parent | on HN ]