Front Cover.png

What is the P vs. NP problem?

What is the P vs. NP problem? In simple words, it translates to the following question: Whether every problem whose solution can be quickly verified (NP) can also be solved quickly (P)? For instance, we can know at a glance if a Sudoku grid or a Rubik's cube is already solved. But does it mean we can solve it quickly too?

 

Apart from being one of the biggest mysteries in Computer Science,  the P vs. NP Problem also has a deeper philosophical connection. The discovery of this problem is the culmination of an arduous journey that an entire tribe pursued in the twentieth century to arrive at a theory that would explain everything. The tribe included philosophers, mathematicians, logicians, and computer scientists. It was a journey filled with frustrations and triumphs. It was a journey that humbled some of the brightest minds on this planet. It was also a journey that was both an accomplishment and a failure. This book is not an attempt to offer a solution but to take you through the journey.