View:

- no detail
- some detail
- full detail

## Proving P ≠ NP

*Lance Fortnow*

### in The Golden Ticket: P, NP, and the Search for the Impossible

- 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 Languages

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

## The Golden Ticket: P, NP, and the Search for the Impossible

*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 Languages

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 Golden Ticket

*Lance Fortnow*

### in The Golden Ticket: P, NP, and the Search for the Impossible

- 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 Languages

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

## The Future

*Lance Fortnow*

### in The Golden Ticket: P, NP, and the Search for the Impossible

- 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.0010
- Subject:
- Computer Science, Programming Languages

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 ... More

## The Prehistory of P versus NP

*Lance Fortnow*

### in The Golden Ticket: P, NP, and the Search for the Impossible

- 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.0005
- Subject:
- Computer Science, Programming Languages

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 ... More

View:

- no detail
- some detail
- full detail