Computational Complexity: A Conceptual Perspective
Computational Complexity: A Conceptual Perspective
by Oded Goldreich
eBook Details:
Publisher: Cambridge University Press 2008
ISBN/ASIN: 052188473X
ISBN-13: 9780521884730
Number of pages: 632
License(s): Copyright 2006 by Oded Goldreich.
Permission to make copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro t or commercial advantage and that new copies bear this notice and the full citation on the rst page. Abstracting with credit is permitted.
eBook Description:
This book offers a comprehensive perspective to modern topics in complexity theory, which is a central field of the theoretical foundations of computer science. It addresses the looming question of what can be achieved within a limited amount of time with or without other limited natural computational resources. The book can be used as an introduction for advanced undergraduate and graduate students as either a textbook or for self-study, or to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems.
