1 (p1): 1 Introduction and Preliminaries 1 (p2): 1.1 Introduction 2 (p3): 1.1.1 A Brief Overview of Complexity Theory 6 (p4): 1.1.2 Characteristics of Complexity Theory 8 (p5): 1.1.3 Contents of This Book 12 (p6): 1.1.4 Approach and Style of This Book 16 (p7): 1.1.5 Standard Notations and Other Conventions 17 (p8): 1.2 Computational Tasks and Models 18 (p9): 1.2.1 Representation 18 (p10): 1.2.2 Computational Tasks 20 (p11): 1.2.3 Uniform Models(Algorithms) 36 (p12): 1.2.4 Non-uniform Models(Circuits and Advice) 42 (p13): 1.2.5 Complexity Classes 43 (p14): Chapter Notes 44 (p15): 2 P,NP,and NP-Completeness 46 (p16): 2.1 The P Versus NP Question 47 (p17): 2.1.1 The Search Version:Finding Versus Checking 50 (p18): 2.1.2 The Decision Version:Proving Versus Verifying 54 (p19): 2.1.3 Equivalence of the Two Formulations 55 (p20): 2.1.4 Two Technical Comments Regarding NP 55 (p21): 2.1.5 The Traditional Definition of NP 57 (p22): 2.1.6 In Support of P Different from NP 58 (p23): 2.1.7 Philosophical Meditations 58 (p24): 2.2 Polynomial-Time Reductions 59 (p25): 2.2.1 The General Notion of a Reduction 61 (p26): 2.2.2 Reducing Optimization Problems to Search Problems 63 (p27): 2.2.3 Self-Reducibility of Search Problems 67 (p28): 2.2.4 Digest and General Perspective 67 (p29): 2.3 NP-Completeness 68 (p30): 2.3.1 Definitions 69 (p31): 2.3.2 The Existence of NP-Complete Problems 71 (p32): 2.3.3 Some Natural NP-Complete Problems 81 (p33): 2.3.4 NP Sets That Are Neither in P nor NP-Complete 85 (p34): 2.3.5 Reflections on Complete Problems 87 (p35): 2.4 Three Relatively Advanced Topics 87 (p36): 2.4.1 Promise Problems 92 (p37): 2.4.2 Optimal Search Algorithms for NP 94 (p38): 2.4.3 The Class coNP and Its Intersection with NP 97 (p39): Chapter Notes 99 (p40): Exercises 108 (p41): 3 Variations on P and NP 108 (p42): 3.1 Non-uniform Polynomial Time (P/poly) 109 (p43): 3.1.1 Boolean Circuits 111 (p44): 3.1.2 Machines That Take Advice 113 (p45): 3.2 The Polynomial-Time Hierarchy(PH) 114 (p46): 3.2.1 Alternation of Quantifiers 117 (p47): 3.2.2 Non-deterministic Oracle Machines 119 (p48): 3.2.3 The P/poly Versus NP Question and PH 121 (p49): Chapter Notes 122 (p50): Exercises 127 (p51): 4 More Resources,More Power? 128 (p52): 4.1 Non-uniform Complexity Hierarchies 129 (p53): 4.2 Time Hierarchies and Gaps 129 (p54): 4.2.1 Time Hierarchies 136 (p55): 4.2.2 Time Gaps and Speedup 139 (p56): 4.3 Space Hierarchies and Gaps 139 (p57): Chapter Notes 140 (p58): Exercises 143 (p59): 5 Space Complexity 144 (p60): 5.1 General Preliminaries and Issues 144 (p61): 5.1.1 Important Conventions 145 (p62): 5.1.2 On the Minimal Amount of Useful Computation Space 146 (p63): 5.1.3 Time Versus Space 153 (p64): 5.1.4 Circuit Evaluation 153 (p65): 5.2 Logarithmic Space 154 (p66): 5.2.1 The Class L 154 (p67): 5.2.2 Log-Space Reductions 155 (p68): 5.2.3 Log-Space Uniformity and Stronger Notions 155 (p69): 5.2.4 Undirected Connectivity 162 (p70): 5.3 Non-deterministic Space Complexity 162 (p71): 5.3 Two Models 164 (p72): 5.3.2 NL and Directed Connectivity 171 (p73): 5.3.3 A Retrospective Discussion 172 (p74): 5.4 PSPACE and Games 175 (p75): Chapter Notes 175 (p76): Exercises 184 (p77): 6 Randomness and Counting 185 (p78): 6.1 Probabilistic Polynomial Time 186 (p79): 6.1.1 Basic Modeling Issues 189 (p80): 6.1.2 Two-Sided Error:The Complexity Class BPP 193 (p81): 6.1.3 One-Sided Error:The Complexity Classes RP and coRP 199 (p82): 6.1.4 Zero-Sided Error:The Complexity Class ZPP 199 (p83): 6.1.5 Randomized Log-Space 202 (p84): 6.2 Counting 202 (p85): 6.2.1 Exact Counting 211 (p86): 6.2.2 Approximate Counting 217 (p87): 6.2.3 Searching for Unique Solutions 220 (p88): 6.2.4 Uniform Generation of Solutions 227 (p89): Chapter Notes 230 (p90): Exercises 241 (p91): 7 The Bright Side of Hardness 242 (p92): 7.1 One-Way Functions 243 (p93): 7.1.1 Generating Hard Instances and One-Way Functions 245 (p94): 7.1.2 Amplification of Weak One-Way Functions 250 (p95): 7.1.3 Hard-Core Predicates 255 (p96): 7.1.4 Reflections on Hardness Amplification 255 (p97): 7.2 Hard Problems in E 257 (p98): 7.2.1 Amplification with Respect to Polynomial-Size Circuits 270 (p99): 7.2.2 Amplification with Respect to Exponential-Size Circuits 277 (p100): Chapter Notes 278 (p101): Exercises 284 (p102): 8 Pseudorandom Generators 285 (p103): Introduction 288 (p104): 8.1 The General Paradigm 290 (p105): 8.2 General-Purpose Pseudorandom Generators 291 (p106): 8.2.1 The Basic Definition 292 (p107): 8.2.2 The Archetypical Application 295 (p108): 8.2.3 Computational Indistinguishability 299 (p109): 8.2.4 Amplifying the Stretch Function 301 (p110): 8.2.5 Constructions 304 (p111): 8.2.6 Non-uniformly Strong Pseudorandom Generators 305 (p112): 8.2.7 Stronger Notions and Conceptual Reflections 307 (p113): 8.3 Derandomization of Time-Complexity Classes 308 (p114): 8.3.1 Defining Canonical Derandomizers 310 (p115): 8.3.2 Constructing Canonical Derandomizers 313 (p116): 8.3.3 Technical Variations and Conceptual Reflections 315 (p117): 8.4 Space-Bounded Distinguishers 316 (p118): 8.4.1 Definitional Issues 318 (p119): 8.4.2 Two Constructions 325 (p120): 8.5 Special-Purpose Generators 326 (p121): 8.5.1 Pairwise Independence Generators 329 (p122): 8.5.2 Small-Bias Generators 332 (p123): 8.5.3 Random Walks on Expanders 334 (p124): Chapter Notes 337 (p125): Exercises 349 (p126): 9 Probabilistic Proof Systems 350 (p127): Introduction and Preliminaries 352 (p128): 9.1 Interactive Proof Systems 352 (p129): 9.1.1 Motivation and Perspective 354 (p130): 9.1.2 Definition 357 (p131): 9.1.3 The Power of Interactive Proofs 363 (p132): 9.1.4 Variants and Finer Structure:An Overview 366 (p133): 9.1.5 On Computationally Bounded Provers:An Overview 368 (p134): 9.2 Zero-Knowledge Proof Systems 369 (p135): 9.2.1 Definitional Issues 372 (p136): 9.2.2 The Power of Zero-Knowledge 378 (p137): 9.2.3 Proofs of Knowledge-A Parenthetical Subsection 380 (p138): 9.3 Probabilistically Checkable Proof Systems 381 (p139): 9.3.1 Definition 383 (p140): 9.3.2 The Power of Probabilistically Checkable Proofs 398 (p141): 9.3.3 PCP and Approximation 401 (p142): 9.3.4 More on PCP Itself:An Overview 404 (p143): Chapter Notes 406 (p144): Exercises 416 (p145): 10 Relaxing the Requirements 417 (p146): 10.1 Approximation 418 (p147): 10.1.1 Search or Optimization 423 (p148): 10.1.2 Decision or Property Testing 428 (p149): 10.2 Average-Case Complexity 430 (p150): 10.2.1 The Basic Theory 442 (p151): 10.2.2 Ramifications 451 (p152): Chapter Notes 453 (p153): Exercises 461 (p154): Epilogue 463 (p155): Appendix A:Glossary of Complexity Classes 463 (p156): A.1 Preliminaries 464 (p157): A.2 Algorithm-Based Classes 464 (p158): A.2.1 Time Complexity Classes 467 (p159): A.2.2 Space Complexity Classes 467 (p160): A.3 Circuit-Based Classes 469 (p161): Appendix B:On the Quest for Lower Bounds 469 (p162): B.1 Preliminaries 471 (p163): B.2 Boolean Circuit Complexity 472 (p164): B.2.1 Basic Results and Questions 473 (p165): B.2.2 Monotone Circuits 473 (p166): B.2.3 Bounded-Depth Circuits 474 (p167): B.2.4 Formula Size 475 (p168): B.3 Arithmetic Circuits 476 (p169): B.3.1 Univariate Polynomials 476 (p170): B.3.2 Multivariate Polynomials 478 (p171): B.4 Proof Complexity 480 (p172): B.4.1 Logical Proof Systems 480 (p173): B.4.2 Algebraic Proof Systems 481 (p174): B.4.3 Geometric Proof Systems 482 (p175): Appendix C:On the Foundations of Modern Cryptography 482 (p176): C.1 Introduction and Preliminaries 483 (p177): C.1.1 The Underlying Principles 485 (p178): C.1.2 The Computational Model 486 (p179): C.1.3 Organization and Beyond 487 (p180): C.2 Computational Difficulty 487 (p181): C.2.1 One-Way Functions 489 (p182): C.2.2 Hard-Core Predicates 490 (p183): C.3 Pseudorandomness 490 (p184): C.3.1 Computational Indistinguishability 491 (p185): C.3.2 Pseudorandom Generators 492 (p186): C.3.3 Pseudorandom Functions 494 (p187): C.4 Zero-Knowledge 494 (p188): C.4.1 The Simulation Paradigm 494 (p189): C.4.2 The Actual Definition 495 (p190): C.4.3 A General Result and a Generic Application 497 (p191): C.4.4 Definitional Variations and Related Notions 500 (p192): C.5 Encryption Schemes 502 (p193): C.5.1 Definitions 504 (p194): C.5.2 Constructions 505 (p195): C.5.3 Beyond Eavesdropping Security 507 (p196): C.6 Signatures and Message Authentication 508 (p197): C.6.1 Definitions 509 (p198): C.6.2 Constructions 511 (p199): C.7 General Cryptographic Protocols 512 (p200): C.7.1 The Definitional Approach and Some Models 517 (p201): C.7.2 Some Known Results 517 (p202): C.7.3 Construction Paradigms and Two Simple Protocols 522 (p203): C.7.4 Concluding Remarks 523 (p204): Appendix D:Probabilistic Preliminaries and Advanced Topics in Randomization 523 (p205): D.1 Probabilistic Preliminaries 523 (p206): D.1.1 Notational Conventions 524 (p207): D.1.2 Three Inequalities 528 (p208): D.2 Hashing 528 (p209): D.2.1 Definitions 529 (p210): D.2.2 Constructions 529 (p211): D.2.3 The Leftover Hash Lemma 533 (p212): D.3 Sampling 533 (p213): D.3.1 Formal Setting 534 (p214): D.3.2 Known Results 535 (p215): D.3.3 Hitters 536 (p216): D.4 Randomness Extractors 537 (p217): D.4.1 Definitions and Various Perspectives 541 (p218): D.4.2 Constructions 545 (p219): Appendix E:Explicit Constructions 546 (p220): E.1 Error-Correcting Codes 546 (p221): E.1.1 Basic Notions 547 (p222): E.1.2 A Few Popular Codes 551 (p223): E.1.3 Two Additional Computational Problems 553 (p224): E.1.4 A List-Decoding Bound 554 (p225): E.2 Expander Graphs 555 (p226): E.2.1 Definitions and Properties 561 (p227): E.2.2 Constructions 566 (p228): Appendix F:Some Omitted Proofs 566 (p229): F.1 Proving That PH Reduces to #P 572 (p230): F.2 Proving That IP(f)？AM(O(f))？AM(f) 572 (p231): F.2.1 Emulating General Interactive Proofs by AM-Games 578 (p232): F.2.2 Linear Speedup for AM 583 (p233): Appendix G:Some Computational Problems 583 (p234): G.1 Graphs 585 (p235): G.2 Boolean Formulae 586 (p236): G.3 Finite Fields,Polynomials,and Vector Spaces 587 (p237): G.4 The Determinant and the Permanent 587 (p238): G.5 Primes and Composite Numbers 589 (p239): Bibliography 601 (p240): Index

Complexity theory is a central field of the theoretical foundations of computer science. It is concerned with the general study of the intrinsic complexity of computational tasks; that is, it addresses the question of what can be achieved within limited time (and/or with other limited natural computational resources). This book offers a conceptual perspective on complexity theory. It is intended to serve as an introduction for advanced undergraduate and graduate students, either as a textbook or for self-study. The book will also be useful to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems. In each case, the author starts by posing the intuitive questions that are addressed by the sub-area and then discusses the choices made in the actual formulation of these questions, the approaches that lead to the answers, and the ideas that are embedded in these answers.

Complexity theory is a central field of the theoretical foundations of computer science. It is concerned with the general study of the intrinsic complexity of computational tasks; that is, it addresses the question of what can be achieved within limited time (and/or with other limited natural computational resources). This book offers a conceptual perspective on complexity theory. It is intended to serve as an introduction for advanced undergraduate and graduate students, either as a textbook or for self-study. The book will also be useful to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems. In each case, the author starts by posing the intuitive questions that are addressed by the sub-area and then discusses the choices made in the actual formulation of these questions, the approaches that lead to the answers, and the ideas that are embedded in these answers.