Pages

November 23, 2015

P vs NP, NP Complete and NP hard - most of students think they got it

Many people get the P vs NP Part, but they begin to loose when it comes to NP Complete and NP Hard.

It fascinating to know that there are bounds to computation we perform and the computing world. If someone proves P = NP then the whole world system of economics, finance, scientific especially politics will collapse over night. Why you ask?Because by the class of complexities if P = NP, then it is possible to model a problem with unknown solution to a problem with known solution and get the result by polynomial transformation. So today the computing world and everthing that is based on it i.e.(Banking, ecommerce, internet, secured communications) all run on the fact that few problem are not solvable easily e.g. Cryptography is all based on this, you can't easily find whether a large given number (more than 1000, 2000 digits) is prime of not.

The mathematical and scientific community is divided in this respect. Few say they are same, few say they aren't, and all the major remaining don't know (like me). If someone comes up with a proof of P != NP, then he will bag the 1 million dollar award from clay math institute (http://www.claymath.org/millennium-problems/p-vs-np-problem ), but if someone is able to prove P = NP, then he can take the rest remaining 5 million dollars too with him, since that would lead to solve all the remaining problems.

But there is hope that P is not NP.  S. A. Cook predicted that[1]
Someone will give a sound proof that P is not NP, sometime in the next 20 years.
Also if P is not equal to NP then we have just found a bound to human intelligence too and we can't go beyond a fixed magnitudes of the computing power we see today.

 Food for thought: P vs NP by Vijaya Ramchandran https://www.youtube.com/watch?v=d3nbtuVy6d8


References :
[1]: http://www.ijser.org/researchpaper%5CHistory-of-P-versus-NP-Problem.pdf

No comments:

Post a Comment