Jump to ContentJump to Main Navigation

You are looking at 1-5 of 5 items

  • Keywords: Hamiltonian path x
Clear All Modify Search

View:

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: