View:

- no detail
- some detail
- full detail

## Prologue

*Cristopher Moore and Stephan Mertens*

### in The Nature of Computation

- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780199233212
- eISBN:
- 9780191775079
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199233212.003.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

This prologue begins by considering three examples to demonstrate that in order to solve different problems, fundamentally different kinds of search and different types of proof are required. The ... More

## Needles in a Haystack: the Class NP

*Cristopher Moore and Stephan Mertens*

### in The Nature of Computation

- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780199233212
- eISBN:
- 9780191775079
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199233212.003.0004
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

NP refers to a class of decision problems in which yes-instances are easy to verify. That is: a decision problem is in NP if, whenever the answer for a particular instance is ‘yes’, there is a simple ... More

## Who is the Hardest One of All? NP-Completeness

*Cristopher Moore and Stephan Mertens*

### in The Nature of Computation

- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780199233212
- eISBN:
- 9780191775079
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199233212.003.0005
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

There are problems that cannot be solved, including 3-SAT, graph coloring, and Hamiltonian path. Each of these problems has the remarkable ability to express all the others, or any other problem in ... More

## The Hardest Problems in 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.0004
- Subject:
- Computer Science, Programming Languages

This chapter looks at some of the hardest problems in NP. Most of the NP problems that people considered in the mid-1970s either turned out to be NP-complete or people found efficient algorithms ... More

## The Basics

*Cristopher Moore and Stephan Mertens*

### in The Nature of Computation

- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780199233212
- eISBN:
- 9780191775079
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199233212.003.0002
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

This chapter discusses the complexity of a problem by thinking about the best possible algorithm, or computer program, that solves it. It shows that computational complexity theory is not about how ... More

View:

- no detail
- some detail
- full detail