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

Steven Homer (Author), Alan L. Selman (Author)

Book Description

ISBN-10: 0387950559 | ISBN-13: 978-0387950556 | Publication Date: June 21, 2001 | Edition: 1

Intended for use in an introductory graduate course in theoretical computer science, this text contains material that should be core knowledge in the theory of computation for all graduates in computer science. It is self-contained and is best suited for a one semester course. The text starts with classical computability theory which forms the basis for complexity theory. This has the pedagogical advantage that students learn a qualitative subject before advancing to a quantitative one. Since this is a graduate course, students should have some knowledge of such topics as automata theory, formal languages, computability theory, or complexity theory.

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 Details

• Hardcover: 207 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.7 out of 5 stars  See all reviews (10 customer reviews)
• Amazon Best Sellers Rank: #1,494,479 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

5 of 5 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 (San Diego, CA, USA) - See all my reviews
(REAL NAME)   

This review is from: Computability and Complexity Theory (Texts in Computer Science) (Hardcover)

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.

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

This review is from: Computability and Complexity Theory (Texts in Computer Science) (Hardcover)

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)   

Amazon Verified Purchase

This review is from: Computability and Complexity Theory (Texts in Computer Science) (Hardcover)

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.