Jump to ContentJump to Main Navigation
The Nature of Computation$
Users without a subscription are not able to see the full content.

Cristopher Moore and Stephan Mertens

Print publication date: 2011

Print ISBN-13: 9780199233212

Published to Oxford Scholarship Online: December 2013

DOI: 10.1093/acprof:oso/9780199233212.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2020. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 13 August 2020



(p.1) Chapter 1 Prologue
The Nature of Computation

Cristopher Moore

Stephan Mertens

Oxford University Press

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 first example deals with the nature of computation with a walk through the eighteenth-century town of Königsberg (now Kaliningrad), which had seven bridges connecting the two banks of the river Pregel with two islands. A popular puzzle of the time was whether it is possible to walk through the city by crossing each bridge only once. This puzzle was solved by Leonhard Euler in 1736 in the form of a theorem which states that: A connected graph contains an Eulerian cycle if and only if every vertex has even degree. If exactly two vertices have odd degree, it contains an Eulerian path but not an Eulerian cycle. The second example deals with Hamiltonian paths or cycles, while the third involves factoring integers and chess problems. This book explores how to solve problems as efficiently as possible — and how, and why, some problems are extremely hard.

Keywords:   problems, proof, computation, Leonhard Euler, theorem, graph, vertices, Eulerian path, Hamiltonian paths, integers

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .