How to Cure Cancer by Solving Sudokus: A Story about P and NP

Yes, the title of the article might not make much sense. What is the correlation between Sudoku and curing cancer? Can you really cure cancer by solving a Sudoku puzzle? Yes. In fact, solving Sudokus and curing cancer is ‘fundamentally’ the same problem. Thus, if you can find an efficient way to solve a Sudoku, you technically have also discovered the cure to cancer. However, to fully understand this, we need to look at the nature of problems themselves. 

The Realm of Problems

You and I face problems every day. Some of these problems can be very easy to solve, while some might be impossible. In the field of maths and computer science, problems are categorized based on their ‘difficulties’. The most basic categories are P and NP. The origins of P and NP started during the early days of computational engines. Computers were first made to be able to solve all problems in the world. Thus, the programmers of the world began to code their programs. The first time a person created a program to solve a problem, it might be extremely slow and inefficient. However, more people will find clever ways to solve the problem, making it a more efficient and fast program. This is extremely important in the olden days of slow and large computers. 

Most of the initially difficult problems that these programmers faced are found to have easy and efficient solutions. However, they eventually realized that some of these problems are just impossible to optimize. For example, solving arithmetic problems is very fast and easy. On the other hand, it is almost impossible to have a program that will play perfect chess. Thus, they began classifying these problems into P and NP. 

P and NP

P is a class of problems that can be solved in polynomial time. In simpler terms, P includes all the solvable and relatively easy problems. Therefore, P includes problems such as sorting and arithmetic, as previously mentioned. NP is a little bit more difficult to explain, so bear with me. NP is a class of problems that, if given the solution, can at least be checked with relative ease. It might be very difficult for us to find a solution to an NP problem, but checking if a solution is correct will not take much effort. For example, there is no doubt programming a computer to solve a Sudoku puzzle can be very difficult. However, a program that checks whether a completed Sudoku puzzle is correct can be coded by any first-year computer science student. 

Furthermore, P also is a subset of NP, as illustrated in the diagram above. In other words, NP contains all the problems in P. However, it also means that NP contains all the problems outside of P, which are the difficult and ‘unsolvable’ problems. For example, arithmetics is both a P and an NP problem. A computer can calculate a 1+1 problem, which is a P problem. It can also easily check if 1+1 = 2, an NP problem.

There are also problems which are outside of NP, which means that they are both difficult to solve and check. These problems usually don’t have a ‘clear’ answer and are not decision problems. For example, finding the single best move for a particular position in a chessboard is mostly impossible for a computer to solve.

P vs. NP

Now that we understand what P and NP means, we need to ask whether P = NP. Don’t worry we will get to cancer and Sudoku later. Let’s take the problem of finding prime numbers. Prime numbers are numbers that can only be divided by 1 and itself. For example, 11 is a prime number because we can only divide 11 by 11 and 1. The number 4, on the other hand, is not a prime number because we can divide 4 by 2, which is not itself or 1. Finding primes is not difficult at smaller numbers but can be very impossible when the numbers are very large. Believe it or not, 93371 is a prime number. There is even a race, called the Great Internet Mersenne Prime Search, to find the largest possible prime numbers that exist. For the longest time, people thought that finding primes as an NP problem. But soon, we find efficient algorithms to solve the problem and categorize it to P. So is every problem in NP is equal to P or is there a mysterious divine boundary between the two classes? 

The question of whether P = NP is, in reality, a is difficult to answer. It requires profound knowledge in maths and complexities to fully understand the true scale of this simple-looking problem. In fact, it is one of the 7 questions in the Millennium Problems and solving it has a price of 1 million dollars.

If you want a more in-depth explanation about P vs. NP and complexities, check out the video below.

NP-Complete and Protein Folding

In the early 1960’s complexity researchers found that most of the difficult NP problems they are facing are fundamentally the same problem. Thus, they coined the phrase NP-complete. NP-complete problems are a set outside inside NP but outside of P. The set essentially contains all the ‘hardest’ problems in NP. Furthermore, if you can solve an NP-complete problem in P time, you can use this solution to solve all problems in P and NP. If you haven’t guessed, solving Sudokus is part of NP-complete. Conveniently enough, protein folding is also NP-complete. So if you can solve Sudoku in polynomial time, protein folding can also be solved much more efficiently.

Protein folding is closely related to the formation of cancer cells. It is the process where a 2-dimensional string of protein coils up into 3-dimensional functional protein. If it folds correctly, it performs the standard tasks it should. However, they do not always fold up properly, and one reason for this is a mutation in the protein. Understanding how protein folding works and being able to predict the fold of a protein will be a critical step in finding the cure for cancer. 

Now that you understand NP-completeness and protein folding, I hope you now can see how solving Sudokus can help cure cancer. So, if you do find a very efficient way to play Sudoku, quickly tell everyone.

Featured image by Pixabay