Limits of Computation

<p><strong>Limits of Computation: An Introduction to the Undecidable and the Intractable</strong> offers a gentle introduction to the theory of computational complexity. It explains the difficulties of computation addressing problems that have no algorithm at all and problems that cannot be solved efficiently. </p><p>The book enables readers to understand:</p><ul> <li>What does it mean for a problem to be unsolvable or to be NP-complete?</li> <li>What is meant by a computation and what is a general model of a computer?</li> <li>What does it mean for an algorithm to exist and what kinds of problems have no algorithm?</li> <li>What problems have algorithms but the algorithm may take centuries to finish?</li> </ul><p>Developed from the authors’ course on computational complexity theory the text is suitable for advanced undergraduate and beginning graduate students without a strong background in theoretical computer science. Each chapter presents the fundamentals examples complete proofs of theorems and a wide range of exercises.</p>