Search Results

This chapter focuses on a few of the ideas that people have tried to solve the P versus NP problem. These have not panned out to anything close to a solution to the problem. To prove P ≠ NP one needs to show that no algorithm, even those that have not been discovered yet, can solve some NP problem. It is simply very difficult to show that something cannot be done. However, it is not a logically impossible task. The only known serious approach to the P versus NP problem today is due to Ketan Mulmuley from the University of Chicago. He has shown how solving some difficult problems in a mathematical field called algebraic geometry may lead to a proof that P ≠ NP. However, resolving these algebraic geometry problems will require mathematical techniques far beyond what is available today.

This introductory chapter provides an overview of the P versus NP problem. The P versus NP problem asks, among other things, whether one can quickly find the shortest route for a traveling salesman. P and NP are named after their technical definitions, but it is best not to think of them as mathematical objects but as concepts. “NP” is the collection of problems that have a solution that one wants to find. “P” consists of the problems to which one can find a solution quickly. “P = NP” means one can always quickly compute these solutions, like finding the shortest route for a traveling salesman. “P ≠ NP” means one cannot. Ultimately, the P versus NP problem has achieved the status of one of the great open problems in all of mathematics.

This chapter explores some of today's great challenges of computing. These challenges include parallel computation, dealing with big data, and the networking of everything. The chapter then argues that P versus NP goes well beyond a simple mathematical puzzle. The P versus NP problem is a way of thinking, a way to classify computational problems by their inherent difficulty. P versus NP also brings communities together. There are NP-complete problems in physics, biology, economics, and many other fields. Physicists and economists work on very different problems, but they share a commonality that can give great benefits from sharing tools and techniques. Tools developed to find the ground state of a physical system can help find equilibrium behavior in a complex economic environment. Ultimately, the inherent difficulty of NP problems leads to new technologies.

This chapter explores two separate paths that led to the P versus NP question. In the end it was Steve Cook in the West and Leonid Levin in the East who would first ask whether P = NP. Science does not happen in a vacuum, and both sides have a long history leading to the work of Cook and Levin. The chapter covers just a small part of those research agendas, the struggle in the West to understand efficient computation and the struggle in the East to understand the necessity of perebor. Both would lead to P versus NP. Today, with most academic work available over the Internet and with generally open travel around the world, there is now one large research community instead of two separate ones.