Simply put, the P=NP problem (also known by many as the P versus NP problem or the P vs NP problem) is asking whether a general problem whose solution can be quickly verified by a computer system can also be solved quickly by a computer. Seems easy right? If you can solve a problem quickly, haven’t you also verified the problem as well thus you have done both in the same amount of time? Think about it a little and see just how difficult the problem actually is.
The problem was first discussed in letters between John Forbes Nash Jr and the National Security Agency as well as letters between Kurt Godel to John Von Neumann which took place in the 1950s. The problem, moreover, was formally introduced when Stephen Cook created his paper, “The Complexity of Theorem Proving Procedure,” in 1971. This issue is so hefty that the person who solves it correctly will receive 1 million dollars. Technically the issue “started” in the 1950s and has been unsolved ever since. That is 67 years in 2017 that we have been having computer issues which is longer than the show “Doctor Who” has been running considering the show has been on for just over 50 years now.
“P” in the equation symbolizes the computer solving a problem. “NP,” on the other hand, is the computer verifying the solution to the equation. Time is also an element except for the fact that the equation runs in polynomial time rather than standard time. An equation is solvable in polynomial time if the number of steps taken for a given input is O(n^k) where k is a nonnegative integer and n is the complexity of the given input. Polynomial time is very fast which is the reason that the simple definition for P=NP involves the word “quickly.”
The question is: “is P equal to NP?” In a poll of 100 researchers (which took place in 2002), 61% of people said no, 9% said yes, 22% claimed they were unsure and 8% believed that the two elements had no correlation making the question impossible to prove or disprove. This survey data shows how controversial and hard to prove this problem is. The same poll was used in 2012 with 151 people. This time, 83% said no, 9% said yes, 3% said there was no correlation and 5% claimed they either didn’t know or didn’t care.
When it comes to these kinds of debateable algorithms, it is best that researchers explore all sides of the arguments that are presented to them in order to understand how other people think. In any field you need to think openly instead of only sticking to your opinions. In this case, it is great to understand why people think P is not equal to P, why it the two are equal, as well as why the two are not correlated. This type of thinking could lead to the problem being solved, or was it that the problem needs to be verified?