Lance Fortnow
- Published in print:
- 2017
- Published Online:
- May 2018
- ISBN:
- 9780691175782
- eISBN:
- 9781400846610
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691175782.003.0007
- Subject:
- Computer Science, Programming
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 ...
More
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.Less
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.
Lance Fortnow
- Published in print:
- 2017
- Published Online:
- May 2018
- ISBN:
- 9780691175782
- eISBN:
- 9781400846610
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691175782.003.0001
- Subject:
- Computer Science, Programming
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. ...
More
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.Less
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.
Lance Fortnow
- Published in print:
- 2017
- Published Online:
- May 2018
- ISBN:
- 9780691175782
- eISBN:
- 9781400846610
- Item type:
- book
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691175782.001.0001
- Subject:
- Computer Science, Programming
The P versus NP problem is the most important open problem in computer science, if not all of mathematics. Simply stated, it asks whether every problem whose solution can be quickly checked by ...
More
The P versus NP problem is the most important open problem in computer science, if not all of mathematics. Simply stated, it asks whether every problem whose solution can be quickly checked by computer can also be quickly solved by computer. This book provides a nontechnical introduction to P versus NP, its rich history, and its algorithmic implications for everything we do with computers and beyond. The book traces the history and development of P versus NP, giving examples from a variety of disciplines, including economics, physics, and biology. It explores problems that capture the full difficulty of the P versus NP dilemma, from discovering the shortest route through all the rides at Disney World to finding large groups of friends on Facebook. The book explores what we truly can and cannot achieve computationally, describing the benefits and unexpected challenges of this compelling problem.Less
The P versus NP problem is the most important open problem in computer science, if not all of mathematics. Simply stated, it asks whether every problem whose solution can be quickly checked by computer can also be quickly solved by computer. This book provides a nontechnical introduction to P versus NP, its rich history, and its algorithmic implications for everything we do with computers and beyond. The book traces the history and development of P versus NP, giving examples from a variety of disciplines, including economics, physics, and biology. It explores problems that capture the full difficulty of the P versus NP dilemma, from discovering the shortest route through all the rides at Disney World to finding large groups of friends on Facebook. The book explores what we truly can and cannot achieve computationally, describing the benefits and unexpected challenges of this compelling problem.
