This book is a highly accessible introduction to the theory of computation. It aims to educate the reader on the most fundamental aspects of algorithms and computation. It deals with two big questions: Which problems admit no algorithm? Which kind of problems cannot be solved efficiently?

Chapter 1 introduces the fundamentals of set theory that are used in subsequent chapters. Chapter 2 outlines some basics of automata theory and defines alphabets, strings, languages, operations on strings, and operations on languages. Chapter 3, one of the central chapters, addresses computational problems, the importance of polynomial-time algorithms, and the fundamentals of asymptotic running time. In chapter 4, the authors present Turing machines as universal models of computation. Chapter 5 further elaborates on Turing machines and presents the concept of Turing completeness. In chapter 6, the authors provide an interesting and effective discussion of the fact that certain languages are undecidable. Chapter 7 presents the concept of reducibility between languages and how reducibility from one language to another can be used to infer properties of each. Chapters 8 to 10 focus on computational complexity classes, in particular P, NP, and NP-complete problems. Chapter 10 also discusses other complexity notions such as co-NP, co-NP-complete, strongly NP-complete, PSPACE-complete, and so on. The authors consider the possible relations between complexity classes and the outstanding open questions in complexity theory.

As a computer science (CS) undergrad, I studied various textbooks on automata and computational complexity. This book is an easy and highly accessible version of some of those classic books. The authors have targeted “advanced undergraduates or beginning graduate students who may not have a strong background in theoretical [CS].” This book could easily serve in a first-year CS course to gently introduce the most fundamental concepts in the theory of computation. The writing is so accessible that even a layperson with some mathematical maturity could enjoy it. For example, when presenting undecidable problems, the authors first present Russell’s barber paradox (the barber who shaves everyone who does not shave himself). The style is almost conversational, but with just the right amount of formality to illuminate important concepts. It is a great way to showcase some of the interesting and intellectually appealing aspects of theoretical CS. Despite the informal style, the book covers a lot of ground and presents a number of well-known and important theorems. It is recommended for any CS student.