Alright, its time to dive into one of the big problems facing our society today. Are you ready for this? Drum roll please…

Does P == NP?

Well clearly, P doesn’t equal NP because NP has the extra N before the P. So problem solved, lets all get back to our lives. But wait, hang on a second. These must be variables that mean something else. Well in fact, they do. P is short for ‘Polynomial’ and NP is short for ‘Non-deterministic Polynomial’. What? Don’t worry, I’ll explain.

The point of this question is to determine if all problems are simple to solve or if their exists problems that cannot be solved in a short amount of time. If you remember back to high school math, you’ve most certainly worked with polynomials. Polynomials are functions that involve coefficients and variables, such as x2 . We’ll go back to the math later, as it isn’t really important at this point.

The first important aspect to realize, is that some problems are easy to solve (P-type problems) and others are inherently more difficult to solve (NP-type problems). Okay so right now, you’re probably thinking, ‘Duh, of course some problems are hard… that last problem on the math test kicked my butt’. The solution here is rather clear – study harder for your math test! But that isn’t what defines an NP-type problem.

Think of two numbers being multiplied together, for example:

545 x 193

Solving this is rather simple (as easy as elementary school math!).

Alright, now let me ask you one question. Is multiplication a P-type problem or an NP-type problem? Clearly, its a P-type problem. Even if the two numbers were massive in size, the algorithm doesn’t exactly take exponentially longer. Maybe for you it might take long to multiply:

643246372848 x 473247324987

…but even a one dollar calculator can spit out 304414625257906428752976 almost instantly. The reason for this is that there exists a programmatic algorithm that can multiply extremely large numbers for relatively low ‘cost’. We can check this solution rather easily as well, for example… we could divide the product by any one of the components to get the other. That is what makes multiplication a P-type problem. It is easy to solve and it is easy to check!

Alright, so now comes the kicker. Clearly the factors of this large number are the two we multiplied above. We know this because we’re the one that multiplied them! Now comes the tricky part, lets try and go backwards. What are the factors of:

3044146249869977346133276

Did you figure them out? How about I let you use your computer. Go here and factor it. In fact, please don’t! You’ll lock up the website! The reason is that there doesn’t currently exist an algorithm for factoring extremely large numbers. We can go one way, sure… but going backwards is EXTREMELY difficult. For numbers like 15, we know the factors are 3 and 5. But for numbers that have 20, 40, 100 digits, even our best computers struggle to even come close to solutions.

Factoring is an NP-type problem. Its very hard to solve, but relatively easy to check (just multiply the two numbers together). If you don’t have those two numbers to begin with, you’re in deep !@#$. The reason is because the complexity for factoring grows exponentially ( 2x ) rather than by polynomial growth ( x). As we know, exponential functions will grow immensely faster than polynomials after a certain point. As you can see here, the polynomial loses after (4,16).

 

This right here, is the fundamental problem in computer science. Scientists struggle to figure out whether all problems are P type problems, whereby we just haven’t come up with the most efficient algorithms yet, or perhaps there are problems of type NP (like factoring), where a shortcut doesn’t exist. The applications of solving this are huge! Currently, encryption, protein folding in medical research and navigation problems are all grouped as NP-type problems. If we could prove that P = NP, we could therefore show that the hardest problems DO have simple solutions – we just need to find them!

Simply put, if anyone ever proves whether the hardest problems like folding proteins have shortcuts as solutions, the world would change overnight. Cancer research would catapult into overdrive, internet security would be utterly useless, and a zoo of other problems would finally see solutions! Perhaps one day, we’ll know. Its funny because, the very notion of figuring out whether P = NP is in fact, an NP-type problem… great.

 

Advertisements