Computability and Complexity Theory (Texts in Computer Science) (Hardcover)

~ Steven Homer (Author), Alan L. Selman (Author) "In the next chapter we will become familiar with models of computing..." (more)
Key Phrases: linear speedup theorem, partial computable function, shortest accepting computation, Additional Homework Problems, Program Termination, Euclidean Algorithm (more...)

Editorial Reviews

Review

From the reviews:

"The difference between this new introductory graduate textbook in theoretical computer science and other texts is that the authors have chosen to concentrate on computability theory and computational complexity theory. They motivate this focus by pointing out that most students have been introduced to the theory of automata and formal languages as undergraduates. The topics are treated in depth and in full formal detail. Explicit homework assignments are tightly integrated into the exposition of the material." --Computing Reviews

"This book is intended for use in a modern graduate course in the theory of computing. … Mainly all old classical complexity results as well as a relatively recent result that space-bounded classes are closed under complements are included into the book. The textbook is self-contained. A list of useful homework problems is appended to each chapter. The book is well written and is recommended to students as well as specialists in theoretical computer science." (Anatoly V. Anisimov, Zentralblatt MATH, Vol. 1033 (8), 2004)

"This book is a solid textbook suited for one- or two-semester graduate courses on the theory of computing. …The authors are two leading researchers in the field of theoretical computer sciences, most notably complexity theory. … This textbook is an excellent resource and guide for those looking to develop a solid grounding in the theory of computing. Beginning graduates, advanced undergraduates and professionals involved in theoretical computer science, complexity theory and computability will find this book an essential and practical learning tool." (André Grosse, The Computer Journal, Vol. 45 (4), 2002)

Product Description

This volume introduces materials that are the core knowledge in the theory of computation. The book is self-contained, with a preliminary chapter describing key mathematical concepts and notations and subsequent chapters moving from the qualitative aspects of classical computability theory to the quantitative aspects of complexity theory. Dedicated chapters on undecidability, NP-completeness, and relative computability round off the work, which focuses on the limitations of computability and the distinctions between feasible and intractable.

Topics and features:

*Concise, focused materials cover the most fundamental concepts and results in the field of modern complexity theory, including the theory of NP-completeness, NP-hardness, the polynomial hierarchy, and complete problems for other complexity classes

*Contains information that otherwise exists only in research literature and presents it in a unified, simplified manner; for example, about complements of complexity classes, search problems, and intermediate problems in NP

*Provides key mathematical background information, including sections on logic and number theory and algebra

*Supported by numerous exercises and supplementary problems for reinforcement and self-study purposes.

With its accessibility and well-devised organization, this text/reference is an excellent resource and guide for those looking to develop a solid grounding in the theory of computing. Beginning graduates, advanced undergraduates, and professionals involved in theoretical computer science, complexity theory, and computability will find the book an essential and practical learning tool.

Product Details

• Hardcover: 194 pages
• Publisher: Springer; 1 edition (June 21, 2001)
• Language: English
• ISBN-10: 0387950559
• ISBN-13: 978-0387950556
• Product Dimensions: 10 x 7 x 0.8 inches
• Shipping Weight: 14.4 ounces (View shipping rates and policies)
• Average Customer Review: 2.6 out of 5 stars  See all reviews (8 customer reviews)
• Amazon.com Sales Rank: #1,149,506 in Books (See Bestsellers in Books)

Customer Reviews

Most Helpful Customer Reviews

3 of 3 people found the following review helpful:

3.0 out of 5 stars There are better introductory choices, May 2, 2005

By	Grommit (Morgantown, WV) - See all my reviews

I found this one disapointing. For example, they do a nice job very carefully and clearly distinguishing "decidable" and "acceptable" languages. Then they talk about languages Turing machines "recognize" without saying if these are acceptable or decidable or what. This kind of thing is frustrating. That said, I did learn things from this book. Many things are well covered. But if you buy one book, buy Sipser instead.

2 of 2 people found the following review helpful:

3.0 out of 5 stars NP-hard textbook!, June 2, 2009

By	Z. Rafii (Chicago, IL, USA) - See all my reviews (REAL NAME)

I bought this textbook for my class of Theory of Computation. It is a really hard class, and the material is really difficult to understand, especially when you are new to it. The textbook did not help me at all to understand the course. It is a small textbook, not clear enough, and I think expensive for what it is.

2 of 2 people found the following review helpful:

2.0 out of 5 stars What a textbook shouldn't be, April 2, 2005

By	Kyle A. Wright (Ames, IA, USA) - See all my reviews (REAL NAME)

It's rather disappointing that many universities use this textbook in courses on the subject matter. While it does cover some inseresting and important things, in general the book is terribly written. The back cover states that this text assumes no prerequisites - nothing could be further from the truth. The first chapter purports to provides all prerequisites needed, but it is poorly done and insufficient. Both the first chapter and all subsequent chapters make use of mathematical and computational symbols and terminology that are not explained. Even if you're generally familiar with them, you'll still have to look up the exact definitions in another book. Most of the text in the book is written in a terribly confusing manner that requires it to be re-read multiple times. The proofs are the same way (I have seen some of these proofs written in a very clear manner elsewhere). The authors even omit some proofs because they're "obvious" (although I have been confronted with having to come up with these proofs on graduate-level exams). Possibly the most frustrating thing about this book is the fact that frequently (usually when introducting a new topic) it will give a tiny bit of background and then throw out a few homework problems. Instead of explaining what's going on, the authors decide to let these homework problems take the place of a few pages of definitions, explanations, and examples (note that there are no solutions to the hw problems in the book). Not only will you struggle with the rest of the material if you can't get those problems, but it makes it nearly impossible to merely read the book.