In computer science, the efficiency of algorithms is very important. Most algorithms are said to be “fast” if they can be solved in a standard time called a polynomial. Polynomial time is when a problem can be solved in steps scaled by a polynomial factor given the complexity of the input data. So, let’s say the input complexity is some number n, a polynomial time algorithm will be able to solve the problem in nk steps.

One of the most famous subproblems is NP-complete problems. NP-complete problems are problems that can be quickly checked and can be used to model any other NP-complete problem. Solving one of these problems in polynomial time is therefore a strong incentive to solve P vs. NP. [1]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. [4]

Figure 1. The Million Dollar Problem that could Break Cryptography

Figure 1 shows 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. [2]

Conclude

P vs NP is a critical unsolved problem in computer science that could have drastic implications. Although the great consensus is that P does not equal NP, any commonly accepted proof would shake the scientific world. [3]

References:

1. https://industry-update.com/a-million-dollar-problem-that-could-break-cryptography/97287/
2. https://www.newsreap.com/the-million-dollar-problem-that-could-break-cryptography-scitechdaily/
3. https://techsens.in/the-million-dollar-problem-that-could-break-cryptography/
4. https://scitechdaily.com/the-million-dollar-problem-that-could-break-cryptography/

Cite this article:

Thanusri swetha J (2022), The Million Dollar Problem that could Break Cryptography, Anatechmaz, pp.49