Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

If P = NP were proved to be true, it would tell us that there are solutions to a certain class of problems. Assuming it's true doesn't give us those solutions.

Wikipedia should answer most of your questions regarding the consequences:

http://en.wikipedia.org/wiki/P_%3D_NP#Consequences_of_proof



To be a little more precise, proving P=NP would mean that there are algorithms to solve those problems that take polynomial time (can be calculated with a polynomial).

NP problems can be solved, it's just slow (think brute force method, running through all the possibilities).


Not true. A polynomial time algorithm for NP complete programs is known (if P=NP that is). You just need to prove P=NP to prove that it is polynomial time.

http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-...




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

Search: