P vs. NP
solution runs in polynomial time. If there were an algorithm with polynomial time to solve jigsaw puzzles, then the puzzle would also be in P. As of right now, no known algorithm exists. So how do we go about proving that the problems in NP are also in P? The Cook-Levin Theorem 3 presents an interesting idea. It states that a problem called SAT is the ‘ hardest ’ problem in NP. This means that if we could find a solver for SAT, we could use it to solve any other problem in NP. SAT encapsulates all of the problems inside NP, allowing any problem within NP to be transformed into a version of SAT whether it be our jigsaw problem, prime factorization in cryptography, or trying to find a solution to a level in Mario. With this knowledge, if we can prove that SAT is ‘ easy ’ , then we can prove that any problem in NP is also in P and so, P = NP. On the other hand, If SAT itself is ‘ hard to solve ’ , then P ≠ NP since SAT would be a problem in NP but not in P. This is now a potential vector for us to focus on and figure out whether SAT is ‘ easy ’ . SAT is the Everest of NP. It can represent every other problem within NP which is why it is usually referred as NP-Complete. After SAT was proved to be the hardest problem in NP, many other NP-Complete problems were found. Problems like sudoku are NP-Complete. Sudoku is surprisingly hard for computers to solve. Ironically, current computers can solve a 9x9 sudoku in milliseconds. Unfortunately, these solutions are all exponential time complexity. Theoretically, if one were to find a way to solve sudoku in polynomial time, then one would have found an NP-Complete solution in polynomial time and, like solving SAT, a cascade of dominoes falls, solving all other problems that are in NP and are NP-Complete, proving that P = NP. That’s all this h angs on: sudoku. If P = NP might just seem like an interesting mathematics problem. But it is so much more than that. Our world functions on the premise that P does not and absolutely cannot equal NP. This is what most computer scientists believe to be true, [4] that P ≠ NP. If P does in fact equal NP, it would be a big problem. Online banking and computing works because we know certain problems are very hard for computers to solve, like sudoku, Hamiltonian paths, or prime factorization. Most important encryption methods work because computers are truly bad at finding prime factorizations of large numbers. This allows good one way encryption that is only solvable using keys. If P = NP is in fact true, this means there is a certain ‘ shortcut ’ to this that can be found. Getting the prime factorization of a large number can be done in polynomial time complexity by a computer. This would be catastrophic to the world’s banking system, making the current methods of encryption useless. Not only that, but if P = NP, the definition for P now applies to NP and all NP problems whether sudoku, Hamiltonian paths, subset sums, subgraph isomorphism, RSA encryption and cryptography, matrix multiplication, polynomial integer factorization, real one-way functions, Mario, or any other problem in NP . Solutions to them can all be found in polynomial time. What this means for the world of mathematics and computer science is yet to be known. We are at the edge of a cliff and all it takes is one step. I think Einstein said it best, ‘ No amount of experimentation can ever prove me right; a single experiment can prove me wrong. ’ P vs. NP is the mathematics problem that could change the world.
3 The Cook-Levin Theorem. (2020). [online] . Available at: http://www.cs.toronto.edu/~ashe/cook-levin- handout.pdf. [Accessed 2 Sep. 2021].
159
Made with FlippingBook interactive PDF creator