Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Limits of computation : an introduction to the undecidable and the intractable
Reiter E., Johnson C., Chapman & Hall/CRC, Boca Raton, FL, 2013. 279 pp. Type: Book (978-1-439882-06-1)
Date Reviewed: Jun 24 2013

Reiter and Johnson have produced an excellent but “gentle introduction to the theory of computational complexity,” as they put it. This gentleness is entirely appropriate, given the notoriously nuanced, seemingly imprecise, and often paradoxical nature of computational complexity theory. The cognitive “feel” of complexity theory has, to me, always been somewhat reminiscent of that of Cantor’s transfinite arithmetic [1], which involves rigorous modulo axioms and hypotheses, but can still be slippery, to say the least. I use the word “theory” in only one of its two conventional senses. To me, “theory” denotes a “body of knowledge” [2], but does not include such “theories” as the claim that the moon is made of cheese. Less frivolous and more elaborate examples of hypothesis-intensive pseudo-theories abound, but all this is to make a point: Theories of computational complexity can be crazy-making to those of us who have found refuge in the precision and lack of ambiguity provided by mathematics and computing science in general. This book succeeds in convincing the reader that its subject is indeed a theory worthy of the name, and that students in particular can gain cognitive control of this difficult subject, albeit only by reading “with pencil in hand,” as the authors suggest.

Two mainstays of the book are Turing machines and proofs by contradiction, regarding which there is a get-ready in the preface. Cantor diagonalization also figures large. The book makes no mention of the aversion to such proofs commonly held by constructivists or intuitionists. “To prove something does not exist, assume that it does and arrive at a contradiction.” Chapter 1, “Set Theory,” also displays a nicely constructed bijection from the open interval (0, 1) to R, the entire real line.

“Alphabets, Strings, and Languages,” chapter 2, is an efficient introduction to concepts, such as language as a set of strings over an alphabet; the Kleene star of a language; homomorphisms; prefixes and suffixes; and quotients. This is a buildup to the book’s “basic goal” of precisely defining what it means to “solve a problem,” and what “a problem has no solution” means. The key statement in chapter 3 (“Algorithms”) is that “computational problems can always be restated as decision problems” (that is, as “Yes/No” problems). Of greatest pedagogical value is the explication of the term “reasonable” for polynomial time-complexity: “problems not bounded by a polynomial ... grow so fast that they are absolutely not efficient.” So, “reasonable” really means “not ridiculously unreasonable” (my words). Though the explanation of big-O notation is clear, I’m not sure about the point made on page 47 regarding n log n as O(n2): Is this assertion supposed to be true or false?

Chapter 4 covers Turing machines (TMs) in a clear and uncluttered way. “Theoretical computer science needs a model of a computer--a perfect machine, not dependent on electricity, chip design, or anything that might have a flaw.” A Turing machine accepts, rejects, halts, or loops--nothing else. Favoring solutions that are “decidable” and “acceptable,” over those that have the more obscure traits of being “recursive” and “recursively enumerable,” is very effective, “since we are not dealing with recursion as most computer science students know the term.” Chapter 5 continues with Turing completeness, and introduces nondeterminism. The Church-Turing thesis is shown to mean that “no extension adds any power to the Turing machine, though it may add convenience.”

“Undecidability” and “Undecidability and Reducibility,” chapters 6 and 7, define an algorithm that “decides a language” as always halting in either the accept or reject state. Proof by contradiction in the large is prominent here, and it requires “effort to prove and also understand the proof.” (My party-pooper side suggests that questions regarding the validity of proof by contradiction could also at least be mentioned, but that’s a polemic from an old constructivist/intuitionist hothead.) The tight but elaborate treatment of the Post correspondence problem will certainly help students decide if computation theory is for them. Chapters 8 and 9, on NP, NP-hard, and NP-complete, make a fitting climax to the buildup in the previous chapters. The plain-language characterization of NP as the class of problems with easy-to-check solutions speaks to the book’s excellent pedagogy, and the characterization of NP-hard is as clear as these subtleties can be. The treatment of the Cook-Levin theorem regarding the NP-completeness of a class of Boolean satisfaction problems is a foundation for further study that should be appreciated. The final chapter treats other complexity classes that are “out there,” including complement classes (such as co-NP); space complexity, PSPACE, and NPSPACE; and Savitch’s theorem, which says that NPSPACE = PSPACE.

This book is a very effective hands-on, straight-line treatment of complexity theory, and is a worthy occupant of that niche within this (now) vast body of knowledge.

Reviewer:  George Hacken Review #: CR141307 (1309-0778)
1) Abian, A. The theory of sets and transfinite arithmetic. Saunders, Philadelphia, PA, 1965.
2) Friedberg, R. An adventurer’s guide to number theory. McGraw-Hill, New York, NY, 1968.
Bookmark and Share
  Reviewer Selected
Featured Reviewer
 
 
General (F.1.0 )
 
 
Complexity Measures And Classes (F.1.3 )
 
 
General (F.2.0 )
 
Would you recommend this review?
yes
no
Other reviews under "General": Date
Fundamental physical limitations of the computational process
Landauer R.  Computer culture: the scientific, intellectual, and social impact of the computer (, New York,1701984. Type: Proceedings
Feb 1 1987
Combinatorics, complexity, and randomness
Karp R. Communications of the ACM 29(2): 98-109, 1986. Type: Article
Oct 1 1986
A recursive introduction to the theory of computation
Smith C., Springer-Verlag New York, Inc., Secaucus, NJ, 1994. Type: Book (9780387943329)
Nov 1 1996
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy