P vs NP - The Computational Challenge: From sudoku to cancer research
Sudoku to cancer research? What’s the relation, you might ask. Hold your horses, we’ll get there.
There's a claim that if you can find an efficient way to solve Sudoku faster, you might, technically and indirectly, have also discovered the cure for cancer. But to grasp this, we need to explore how they're related.
About six years ago, while doing some research, I discovered there are seven mathematical problems grouped together and called the Millennium Problems. These are the Birch and Swinnerton-Dyer conjecture, the Hodge conjecture, the Navier–Stokes existence and smoothness, the P versus NP problem, the Riemann hypothesis, the Yang–Mills existence and mass gap, and the Poincaré conjecture. Each of these problems carries a bounty of $1 million if solved. The Poincaré conjecture has already been solved, leaving the remaining six yet to be cracked. But what really caught my interest was the P vs NP problem.
P vs NP
The P vs NP problem is a core topic in computational complexity theory, a branch of theoretical computer science. This problem asks if P = NP. That is, if every problem whose solution can be quickly verified can also be quickly solved.
What are P Problems?
P stands for "polynomial time." Problems in P can be solved by a computer in a reasonable amount of time, usually measured by the size of the input. These are problems that can be solved and verified in polynomial time.
Examples:
Sorting a list of numbers: Algorithms like Merge Sort and Quick Sort have average-case time complexities of O(n log n), which is considered polynomial time.
Searching for an item in a list: Binary search is a classic example of a polynomial-time algorithm, with a time complexity of O(log n).
What are NP Problems?
NP stands for "non-deterministic polynomial time." NP problems are those that can be verified quickly if you have the correct answer but are not necessarily quickly solvable.
Examples:
Traveling Salesman Problem: Finding the shortest route to visit multiple cities.
Sudoku: The grid-based, logic-number placement puzzle.
Sudoku and Cancer: The Connection
Remember the title of this article? Now that you’ve gone back to check it…lol…let’s dive in. How does Sudoku relate to cancer or lead to a cure for cancer?
Sudoku
Sudoku is an NP-complete problem. Why? Given a partially filled grid of numbers, the goal is to complete the grid according to specific rules: each row, column, and NxN grid block must contain all numbers from 1 to 9.
While it's easy to verify if a completed Sudoku grid is correct, finding the solution itself is surprisingly difficult for computers. Even though the rules are simple, the number of possible solutions grows enormously as the grid size increases. This means that solving Sudoku puzzles can be incredibly time-consuming for computers, even with powerful hardware.
In essence, Sudoku is a problem where checking the answer is quick, but finding the answer can be extremely challenging. This places Sudoku in a category of problems called NP-complete, which are notorious for their computational difficulty. Another concept that shares the same NP-complete status is protein folding.
Protein Folding
Protein folding is the process by which a linear chain of amino acids (a polypeptide) assumes a specific three-dimensional structure essential for its function. When this process goes awry (protein misfolding), it can lead to a host of diseases, including cancer. If we could better understand and predict protein folding, we could potentially correct these misfoldings, leading to new cancer treatments. Predicting how proteins fold is computationally intensive and considered an NP-hard problem. Advances in algorithms that can solve NP problems more efficiently could dramatically improve our ability to predict and correct protein folding, leading to breakthroughs in cancer treatment.
The Levinthal paradox, a thought experiment in molecular biology, highlights the improbability of a protein sampling all possible conformations in a reasonable time frame to find its functional form. The paradox illustrates the complexity of protein folding and the efficiency with which biological systems solve this problem. It also raises questions about how nature evolved such efficient mechanisms and whether these principles can be applied to other complex problems.
Conclusion
Now that you understand NP-completeness and protein folding, you can see how solving Sudoku might conceptually help cure cancer. The Levinthal paradox shows us that nature can solve incredibly complex problems efficiently, much like how we hope to tackle NP-complete problems. While the idea that finding a faster way to solve Sudoku could lead directly to a cancer cure is speculative, it highlights the potential of computational breakthroughs to impact medicine.
But the implications of P = NP go beyond just medical research. If this problem were solved, logistics challenges like the Traveling Salesman Problem and the Vehicle Routing Problem would be resolved. Supply chains would be optimized, and there would be enhanced automation and decision-making for AI and machine learning. However, there would also be issues for public-key cryptography. Most public-key cryptographic systems, such as RSA, ECC (Elliptic Curve Cryptography), and DSA (Digital Signature Algorithm), rely on the difficulty of certain mathematical problems (e.g., integer factorization, discrete logarithms) that are currently in NP but not known to be in P. If P = NP, efficient (polynomial-time) algorithms could be found for these problems, potentially breaking the security of these systems.
The current encryption standards would become obsolete, as the fundamental assumption of their security would no longer hold. This would necessitate the development of new cryptographic techniques, possibly based on problems outside of NP or relying on quantum-resistant algorithms. So, if the P vs NP problem is finally solved, it’s going to be a double-edged sword.
Imagine a world where P = NP. The possibilities are staggering—curing diseases, optimizing entire industries, and solving some of humanity's most complex challenges. But with this power comes great responsibility. The same algorithms that could revolutionize medicine could also dismantle the very foundations of our digital security. The line between progress and peril would blur, and society would face choices that could shape the future of humanity.
And now, the rest is up to you. Which edge of the sword will you choose?
References
P vs Np - Clay Mathematics Institute
Protein folding: Levinthal paradox to structure prediction
Introduction to levinthal's protein folding and it's solution
Problems with public key cryptography
P vs Np problem and it's application to public key cryptograhpy