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.
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.
If you think you should have access to this title, please contact your librarian.