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.