目录 About this bOok Acknowledgments Introduction 0 Notational conventions PARTONE: BASIC COMPLEXITY CLASSES 1 The computational model--and why it doesn't matter 2 NP and NP completeness 3 Diagonalization 4 Space complexity 5 The polynomial hierarchy and alternations 6 Boolean circuits 7 Randomized computation 8 Interactive proofs 9 Cryptography 10 Quantum computation 11 PCP theorem and hardness of approximation: An introduction PART TWO: LOWER BOUNDS FOR CONCRETE COMPUTATIONAL MODELS 12 Decision trees 13 Communication complexity 14 Circuit lower bounds: Complexity theory's Waterloo 15 Proof complexity 16 Algebraic computation models PART THREE: ADVANCED TOPICS 17 Complexity of counting 18 Average case complexity: Levin's theory 19 Hardness amplification and error-correcting codes 20 Derandomization 21 Pseudorandom constructions: Expanders and extractors 22 Proofs of PCP theorems and the Fourier transform technique 23 Why are circuit lower bounds so difficult? Appendix: Mathematical background Hints and selected exercises Main theorems and definitions Bibliography Index Complexity class index
占位居中
直播中，去观看