Usually, you can verify a solution to a problem. Whether it’s using multiplication for division or plugging the answer in for a variable, math teachers tell you to check your work using your answer in every school math class.
But let’s say you can verify a solution easily, is it just as easy to solve for that solution? This is the P versus NP problem, a Millenium Prize Problem where the solver will receive a million dollars if valid proof is provided. In computer science, the efficiency of algorithms is very important. Most algorithms are believed to be “fast” if solvable in a standard called polynomial time. Polynomial time is when a problem is solvable in steps scaled by a factor of a polynomial given the complexity of input. So let’s say the complexity of input is some number n, a polynomial time algorithm will be able to solve a problem in nk steps. One of the most prominent subproblems is NP-complete problems. NP-complete problems are ones that can be verified quickly and that can be used to simulate every other NP-complete problem. Therefore, solving one of these problems in polynomial time is a major boost to solving P vs NP.
Cryptography, Some of these problems include games like Battleship and the optimal solution to an NxNxN Rubik’s Cube but also include famous theoretical questions like the traveling salesman problem. If a solution for any of these is found, a general solution for NP-complete problems can also be found. If P is proven to equal NP, there could be serious consequences and benefits. Cybersecurity would be a huge issue as public-key cryptography would be upended and many ciphers could be cracked. However, there would also be improvements in research of protein structure prediction and overall computing because of better integer programming and the solving of the traveling salesman problem. If P is proven to not equal NP, there would be nearly no drawbacks and benefits. Researchers would then focus less on a general solution to all NP-complete problems which would not really change much.
Source: This news is originally published by scitechdaily