 |
GetTextbooks.co.uk
Compare Prices & Save up to 90% |
|
|
|
| Login | Sign up | My Wish List |
 | | Computability and Complexity Theory (Texts in Computer Science) by Steven Homer, Alan L. Selman ISBN-10: 9780387950556 ISBN-10: 0-387-95055-9 ISBN-13: 9780387950556 ISBN-13: 978-0-387-95055-6 Hardcover 2001-06-21 Springer Find Lowest Price |
Editorials | ||
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. | ||
Reviews | ||
We always learn something from a book! In this case, the point to take home is how to not write a book. This book does the worst job of explaining concepts in computability and complexity theory. There is no intuition given behind any of the proofs. Moreover, the language is so bad (I mean way beyond being terse) that most of the times it takes longer to read than it would take to read from another decently written undergraduate text on the same topic/proof. Most of the proofs start with "It is obvious" when it is far from it. It is really sad that such a beautiful subject is treated in such a manner. It is even more sad (and surprising) to see that it is used as the main textbook in a course on complexity theory. I would recommend reading from Sipser or Papadimitriou. | ||
There are better introductory choices 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. | ||
What a textbook shouldn't be 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. | ||
In fact, it is a great and concise book on the subject This book is aimed as an introductory text book on computer science theory. The book is suited for both undergraduate and graduate studies. I would have never expected a book of only a few pages to cover computability and complexity theory basics from introductory undergraduate to early graduate levels. This is because, the author focusses only on core concepts and strives to make them as clear and concise as possible using the power of the mathematical language. It explains the hard theory and logic by easy sentences and words. Even if you use English as foreign language you can read this book by yourself and understand its contents easily having a good background on mathematical language and mathematical thought. | ||
Frustrating. Couldn't they have explained just a little more? I find this book maddening as I try to deciper sometimes cryptic assertions. And once I get stuck it seems I have nowhere to turn. It's not like the local library carries texts on this subject so there's not much easily available for me to supplement this book with, so I'm left to stare at the page for 3 days until I figure it out. | ||