Notes on Computational Complexity Theory CPSC 468/568: Spring 2017 James Aspnes 2017-06-11 11:17 Contents Table of contents i List of figures vii List of tables viii List of algorithms ix Preface x Syllabus xi Lecture schedule xiv 1 Introduction 1 2 Problems and languages 3 3 Models of computation 5 3.1 Turing machines . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.1.1 Computations . . . . . . . . . . . . . . . . . . . . . . . 7 3.1.2 Complexity . . . . . . . . . . . . . . . . . . . . . . . . 7 3.1.2.1 Asymptotic notation . . . . . . . . . . . . . . 8 3.1.3 Programming a Turing machine . . . . . . . . . . . . . 9 3.1.3.1 Example of computing a function . . . . . . 10 3.1.3.2 Example of computing a predicate . . . . . . 12 3.1.4 Turing machine variants . . . . . . . . . . . . . . . . . 12 3.1.5 Limitations of simulations . . . . . . . . . . . . . . . . 16 3.1.6 Universal Turing machines. . . . . . . . . . . . . . . . 19 3.2 Random access machines . . . . . . . . . . . . . . . . . . . . . 20 3.3 The extended Church-Turing thesis . . . . . . . . . . . . . . . 22 i CONTENTS ii 4 Time and space complexity classes 23 5 Nonterminism and NP 25 5.1 Examples of problems in NP . . . . . . . . . . . . . . . . . . 27 5.2 Reductions and NP-complete problems . . . . . . . . . . . . 28 5.3 The Cook-Levin theorem . . . . . . . . . . . . . . . . . . . . 29 5.4 More NP-complete problems . . . . . . . . . . . . . . . . . . 30 5.4.1 1-IN-3 SAT . . . . . . . . . . . . . . . . . . . . . . . . 31 5.4.2 SUBSET SUM and PARTITION . . . . . . . . . . . . 31 5.4.3 Graph problems . . . . . . . . . . . . . . . . . . . . . 33 5.4.3.1 Reductions through INDEPENDENT SET . 33 5.4.3.2 GRAPH 3-COLORABILITY . . . . . . . . . 35 5.5 coNP and coNP-completeness . . . . . . . . . . . . . . . . . 36 5.6 Relation to EXP . . . . . . . . . . . . . . . . . . . . . . . . . 37 6 Diagonalization 38 6.0.1 Undecidability of the Halting Problem . . . . . . . . . 38 6.1 Hierarchy theorems . . . . . . . . . . . . . . . . . . . . . . . . 40 6.1.1 The Space Hierarchy Theorem . . . . . . . . . . . . . 40 6.1.2 The Time Hierarchy Theorem . . . . . . . . . . . . . . 42 6.2 Hierarchy theorems for nondeterminism . . . . . . . . . . . . 46 6.3 Ladner’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . 46 7 Oracles and relativization 50 7.1 Oracle machines . . . . . . . . . . . . . . . . . . . . . . . . . 50 7.2 Relativization . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 7.2.1 The Baker-Gill-Solovay Theorem . . . . . . . . . . . . 51 7.3 The oracle polynomial-time hierarchy . . . . . . . . . . . . . 52 8 Alternation 53 8.1 The alternating polynomial-time hierarchy . . . . . . . . . . . 53 8.2 Equivalence to alternating Turing machines . . . . . . . . . . 54 8.3 Complete problems . . . . . . . . . . . . . . . . . . . . . . . . 55 8.4 Equivalence to oracle definition . . . . . . . . . . . . . . . . . 55 8.5 PH ⊆ PSPACE . . . . . . . . . . . . . . . . . . . . . . . . . 56 9 Space complexity 58 9.1 Space and time . . . . . . . . . . . . . . . . . . . . . . . . . . 59 9.2 PSPACE and TQBF . . . . . . . . . . . . . . . . . . . . . . 59 9.3 Savitch’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . 60 CONTENTS iii 9.4 The Immerman-Szelepcsényi Theorem . . . . . . . . . . . . . 60 9.5 Oracles and space complexity . . . . . . . . . . . . . . . . . . 60 ? ? 9.6 L = NL = AL = P. . . . . . . . . . . . . . . . . . . . . . . . 62 9.6.1 Complete problems with respect to log-space reductions 62 9.6.1.1 Complete problems for NL . . . . . . . . . . 63 9.6.1.2 Complete problems for P . . . . . . . . . . . 64 9.6.2 AL = P . . . . . . . . . . . . . . . . . . . . . . . . . . 65 10 Circuit complexity 67 10.1 Polynomial-size circuits . . . . . . . . . . . . . . . . . . . . . 68 10.1.1 P/poly . . . . . . . . . . . . . . . . . . . . . . . . . . 69 10.1.2 Information-theoretic bounds . . . . . . . . . . . . . . 69 10.1.3 The Karp-Lipton Theorem . . . . . . . . . . . . . . . 70 10.2 Uniformity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 10.3 Bounded-depth circuits . . . . . . . . . . . . . . . . . . . . . 72 10.3.1 Parallel computation and NC . . . . . . . . . . . . . . 73 10.3.2 Relation to L and NL . . . . . . . . . . . . . . . . . . 73 10.3.3 Barrington’s Theorem . . . . . . . . . . . . . . . . . . 74 10.3.4 PARITY 6∈ AC0 . . . . . . . . . . . . . . . . . . . . . 77 10.3.4.1 Håstad’s Switching Lemma . . . . . . . . . . 77 10.3.4.2 Application to PARITY . . . . . . . . . . . . 79 10.3.4.3 Low-degree polynomials . . . . . . . . . . . . 81 11 Natural proofs 84 11.1 Natural properties . . . . . . . . . . . . . . . . . . . . . . . . 84 11.2 Pseudorandom function generators . . . . . . . . . . . . . . . 85 11.3 The Razborov-Rudich Theorem . . . . . . . . . . . . . . . . . 85 11.4 Examples of natural proofs . . . . . . . . . . . . . . . . . . . 86 12 Randomized classes 88 12.1 One-sided error: RP, coRP, and ZPP . . . . . . . . . . . . 88 12.1.1 P ⊆ RP ⊆ NP . . . . . . . . . . . . . . . . . . . . . . 89 12.1.2 Amplification of RP and coRP . . . . . . . . . . . . 89 12.1.3 Las Vegas algorithms and ZPP . . . . . . . . . . . . . 89 12.2 Two-sided error: BPP . . . . . . . . . . . . . . . . . . . . . . 90 12.2.1 Adleman’s Theorem . . . . . . . . . . . . . . . . . . . 91 12.3 The Sipser-Gács-Lautemann Theorem . . . . . . . . . . . . . 92 CONTENTS iv 13 Counting classes 93 13.1 Search problems and counting problems . . . . . . . . . . . . 93 13.1.1 Reductions . . . . . . . . . . . . . . . . . . . . . . . . 94 13.1.2 Self-reducibility . . . . . . . . . . . . . . . . . . . . . . 95 13.2 FP vs #P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 13.3 Arithmetic in #P . . . . . . . . . . . . . . . . . . . . . . . . 97 13.4 Counting classes for decision problems . . . . . . . . . . . . . 97 13.4.1 PP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 13.4.2 ⊕P . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 13.4.3 UP and the Valiant-Vazirani Theorem . . . . . . . . . 98 13.5 Toda’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 99 13.5.1 Reducing from Σ to BPP⊕P . . . . . . . . . . . . . 100 k 13.5.2 Reducing from BPP⊕P to P#P . . . . . . . . . . . . 101 14 Descriptive complexity 102 14.1 First-order logic . . . . . . . . . . . . . . . . . . . . . . . . . . 103 14.2 Second-order logic . . . . . . . . . . . . . . . . . . . . . . . . 104 14.3 Counting with first-order logic . . . . . . . . . . . . . . . . . 105 14.4 Fagin’s Theorem: ESO = NP. . . . . . . . . . . . . . . . . . 106 14.5 Descriptive characterization of PH . . . . . . . . . . . . . . . 107 14.6 Descriptive characterization of NL and L . . . . . . . . . . . 108 14.6.1 Transitive closure operators . . . . . . . . . . . . . . . 108 14.6.2 Arithmetic in FO(DTC) . . . . . . . . . . . . . . . . . 109 14.6.3 Expressing log-space languages . . . . . . . . . . . . . 109 14.6.4 Evaluating FO(TC) and FO(DTC) formulas . . . . . . 110 14.7 Descriptive characterization of PSPACE and P . . . . . . . 111 14.7.1 FO(PFP) = PSPACE . . . . . . . . . . . . . . . . . . 111 14.7.2 FO(LFP) = P . . . . . . . . . . . . . . . . . . . . . . . 112 15 Interactive proofs 113 15.1 Private vs. public coins . . . . . . . . . . . . . . . . . . . . . 114 15.1.1 GRAPH NON-ISOMORPHISM with private coins . . 114 15.1.2 GRAPH NON-ISOMORPHISM with public coins . . 115 15.1.3 Simulating private coins . . . . . . . . . . . . . . . . . 116 15.2 IP = PSPACE . . . . . . . . . . . . . . . . . . . . . . . . . 118 15.2.1 IP ⊆ PSPACE . . . . . . . . . . . . . . . . . . . . . 118 15.2.2 PSPACE ⊆ IP . . . . . . . . . . . . . . . . . . . . . 118 15.2.2.1 Arithmetization of #SAT . . . . . . . . . . . 118 15.2.3 Arithmetization of TQBF . . . . . . . . . . . . . . . . 121 CONTENTS v 16 Probabilistically-checkable proofs and hardness of approxi- mation 124 16.1 Probabilistically-checkable proofs . . . . . . . . . . . . . . . . 125 16.1.1 A probabilistically-checkable proof for GRAPH NON- ISOMORPHISM . . . . . . . . . . . . . . . . . . . . . 125 16.2 NP ⊆ PCP(poly(n),1) . . . . . . . . . . . . . . . . . . . . . 126 16.2.1 QUADEQ . . . . . . . . . . . . . . . . . . . . . . . . . 126 16.2.2 The Walsh-Hadamard Code . . . . . . . . . . . . . . . 127 16.2.3 A PCP for QUADEC . . . . . . . . . . . . . . . . . . 128 16.3 PCP and approximability . . . . . . . . . . . . . . . . . . . . 129 16.3.1 Approximating the number of satisfied verifier queries 129 16.3.2 Gap-preserving reduction to MAX SAT . . . . . . . . 130 16.3.3 Other inapproximable problems . . . . . . . . . . . . . 131 16.4 Dinur’s proof of the PCP theorem . . . . . . . . . . . . . . . 132 16.5 The Unique Games Conjecture . . . . . . . . . . . . . . . . . 134 A Assignments 136 A.1 Assignment 1: due Wednesday, 2017-02-01 at 23:00 . . . . . . 136 A.1.1 Bureaucratic part. . . . . . . . . . . . . . . . . . . . . 136 A.1.2 Binary multiplication . . . . . . . . . . . . . . . . . . 136 A.1.3 Transitivity of O and o . . . . . . . . . . . . . . . . . 139 A.2 Assignment 2: due Wednesday, 2017-02-15 at 23:00 . . . . . . 139 A.2.1 A log-space reduction . . . . . . . . . . . . . . . . . . 139 A.2.2 Limitations of two-counter machines . . . . . . . . . . 140 A better solution: . . . . . . . . . . . . . . . . . 142 A.3 Assignment 3: due Wednesday, 2017-03-01 at 23:00 . . . . . . 142 A.3.1 A balanced diet of hay and needles . . . . . . . . . . . 142 A.3.2 Recurrence . . . . . . . . . . . . . . . . . . . . . . . . 143 A.4 Assignment 4: due Wednesday, 2017-03-29 at 23:00 . . . . . . 144 A.4.1 Finite-state machines that take advice . . . . . . . . . 144 A.4.2 Binary comparisons . . . . . . . . . . . . . . . . . . . 145 A.5 Assignment 5: due Wednesday, 2017-04-12 at 23:00 . . . . . . 146 A.5.1 BPPBPP . . . . . . . . . . . . . . . . . . . . . . . . . 146 A.5.2 coNP vs RP . . . . . . . . . . . . . . . . . . . . . . . 147 A.6 Assignment 6: due Wednesday, 2017-04-26 at 23:00 . . . . . . 147 A.6.1 NP ⊆ PSquareP . . . . . . . . . . . . . . . . . . . . . 147 A.6.2 NL ⊆ P . . . . . . . . . . . . . . . . . . . . . . . . . . 148 A.7 Final Exam . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 A.7.1 LA = PHA . . . . . . . . . . . . . . . . . . . . . . . . 149 A.7.2 A first-order formula for MAJORITY . . . . . . . . . 150 CONTENTS vi A.7.3 On the practical hardness of BPP . . . . . . . . . . . 150 Bibliography 152 Index 157 List of Figures 3.1 Turing-machine transition function for reversing the input, disguised as a C program . . . . . . . . . . . . . . . . . . . . 11 3.2 Recognizing a palindrome using a work tape . . . . . . . . . . 13 vii List of Tables 3.1 Turing-machine transition function for reversing the input . . 10 A.1 Transition table for multiplying by 3 (LSB first) . . . . . . . 138 viii List of Algorithms A.1 Log-space reduction from INDEPENDENT SET to CLIQUE . 141 ix