COMPUTATIONAL COMPLEXITY A Modern Approach

【实例简介】
COMPUTATIONAL COMPLEXITY A Modern Approach。英文正式出版，非draft version
COMPUTATIONAL COMPLEXITY This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory. Requiring essentially no background apart from mathematical maturity, the book can be used as a reference for self-study for anyone interested in complexity, including physicists, mathematicians, and other scientists, as well as a textbook for a variety of courses and seminars. More than 300 exercises are included with a selected hint set The book starts with a broad introduction to the field and progresses to advanced results. Contents include definition of Turing machines and basic time and space complexity classes, probabilistic algorithms, inter- active proofs, cryptography, quantum computation, lower bounds for concrete computational models(decision trees, communication complex ity, constant depth, algebraic and monotone circuits, proof complexity) average-case complexity and hardness amplification, derandomization and pseudorandom constructions, and the PCP Theorem Sanjeev Arora is a professor in the department of computer science at Princeton University. He has done foundational work on probabilistically checkable proofs and approximability of NP-hard problems. He is the founding director of the Center for Computational Intractability, which is funded by the National Science Foundation Boaz Barak is an assistant professor in the department of computer science at Princeton University. He has done foundational work in computational complexity and cryptography, especially in developing"non-blackbox techniques COMPUTATIONAL COMPLEXITY A Modern Approach SANJEEV ARORA Princeton University BOAZ BARAK Princeton University 即罗 CAMBRIDGE UNIVERSITY PRESS CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape town, Singapore, Sao Paulo Cambridge University Press The Edinburgh Building, Cambridge CB2 8RU, UK Published in the United States of america by cambridge university press, New york www.cambridge.org Informationonthistitlewww.cambridge.org/9780521424264 o Sanjeev arora and boaz barak 2009 This publication is in copyright. Subject to statutory exception and to the provision of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press First published in print format 2007 ISBN-13978-0-511-53381-5 e Book(EBL) ISBN-13978-0-521424264 hardback Cambridge University Press has no responsibility for the persistence or accuracy of urls for external or third-party internet websites referred to in this publication and does not guarantee that any content on such websites is, or will remain, accurate or appropriate To our wives-Silvia and ravit Contents About this book page Acknowledgments Introduction 0 Notational conventions 0.1 Representing objects as strings 0.2 Decision problems/languages 0.3 Big-oh notation EXERCISES 4 PART ONE: BASIC COMPLEXITY CLASSES 7 The computational model-and why it doesnt matter 1.1 Modeling computation: What you really need to know 10 1.2 The Turing machine 11 1.3 Efficiency and running time 15 1.4 Machines as strings and the universal Turing machine 19 1.5 Uncomputability: An introduction 1. 6 The Class p 24 1.7 Proof of Theorem 1.9: Universal simulation in O(T log T)-time 29 CHAPTER NOTES AND HISTORY EXERCISES 34 2 NP and NP completeness 38 2.1 The Class NP 39 2.2 Reducibility and NP-completeness 42 2.3 The Cook-Levin Theorem: Computation is local 44 2. 4 The web of reductions 2.5 Decision versus search 54 2.6 CONP EXP and NEXP 2.7 More thoughts about P, NP, and all that CHAPTER NOTES AND HISTORY EXERCISES Contents 3 Diagonalization 3.1 Time Hierarchy Theorem 3.2 Nondeterministic Time hierarchy Theorem 69 3.3 Ladner's Theorem: Existence of NP-intermediate problems 71 3.4 Oracle machines and the limits of diagonalization 72 CHAPTER NOTES AND HISTORY 76 EXERCISES 77 4 Space complexity 4.1 Definition of space-bounded computation 4.2 PSPACE completeness 83 4.3 NL completeness CHAPTER NOTES AND HISTORY EXERCISES 5 The polynomial hierarchy and alternations 5.1 The class∑ 5.2 The polynomial hierarchy 5.3 Alternating Turing machines 5.4 Time versus alternations: Time-space tradeoffs for Sat 101 5.5 Defining the hierarchy via oracle machines CHAPTER NOTES AND HISTORY 104 EXERCISES 104 6 Boolean circuits 106 6.1 Boolean circuits and p/pol 107 6.2 Uniformly generated circuits 6. 3 Turing machines that take advice 112 6. 4 Plpoly and NP 113 6.5 Circuit lower bounds 115 6.6 Nonuniform Hierarchy Theorem 116 6.7 Finer gradations among circuit classes 6. 8 Circuits of exponential size 119 CHAPTER NOTES AND HISTORY 120 EXERCISES 121 7 Randomized computation 123 7.1 Probabilistic Turing machines 124 7.2 Some examples of Ptms 126 7.3 One-sided and"zero-sided" error: RP CoRP. ZPP 131 7. 4 The robustness of our definitions 132 7.5 Relationship between BPP and other classes 135 7. 6 Randomized reductions 13 7.7 Randomized space-bounded computation 139 CHAPTER NOTES AND HISTORY 140 EXERCISES 141 【实例截图】
【核心代码】