xii CONTENTS 16.6.3 Extractors based upon hash functions p16.27(307) 16.6.4 Extractors based upon random walks on expanders.... p16.28(308) 16.6.5 An extractor based upon Nisan-Wigderson p16.28(308) 16.7 Applications of Extractors ......................... .p16.31(311) 16.7.1 Graph constructions p16.31(311) 16.7.2 Running randomized algorithms using weak random sources...... p16.32(312) 16.7.3 Recycling random bits........................ .p16.33(313) l6.7.4 Pseudorandom generators for spacebounded computation······· p16.33(313) Chapter notes and history.....·...·..··.·············· .p16.37(317) Exercises p16.38(318) 17 Hardness Amplification and Error Correcting Codes p17.1(321) 17.1 Hardness and Hardness Amplification.....··..·················pl7.l(321) 17.2 Mild to strong hardness:Yao's XOR Lemma.······..·.······.··.··pl7.2(322) Proof of Yao's XOR Lemma using Impagliazzo's Hardcore Lemma.····· p17.3(323) l7.3 Proof of Impagliazzo's Lemma......·..·..·...·............ .p17.4(324) 17.4 Error correcting codes:the intuitive connection to hardness amplification ... .p17.8(328) 17.4.1 Local decoding..·.······.·················· p17.10(330) 17.5 Constructions of Error Correcting Codes........... p17.12(332) 17.5.1 Walsh-Hadamard Code. p17.12(332) 17.5.2 Reed-Solomon Code p17.13(333) 17.5.3 Concatenated codes p17.14(334) 17.5.4 Reed-Muller Codes. p17.15(335) 17.5.5 Decoding Reed-Solomon.........··. p17.16(336) Randomized interpolation:the case of p <1/(d+1) p17.16(336) Berlekamp-Welch Procedure:the case of p<(m-d)/(2m) p17.16(336) 17.5.6 Decoding concatenated codes.............. p17.17(337) 17.6 Local Decoding of explicit codes... p17.17(337) 17.6.1 Local decoder for Walsh-Hadamard. p17.17(337) 17.6.2 Local decoder for Reed-Muller .p17.18(338) 17.6.3 Local decoding of concatenated codes. p17.19(339) 17.6.4 Putting it all together........... .p17.20(340 17.7 List decoding·.· p17.21(341) 17.7.1 List decoding the Reed-Solomon code···· p17.22(342 17.8 Local list decoding:getting to BPP=P......... p17.23(343) 17.8.1 Local list decoding of the Walsh-Hadamard code... p17.24(344) 17.8.2 Local list decoding of the Reed-Muller code p17.24(344) 17.8.3 Local list decoding of concatenated codes... .p17.26(346) 17.8.4 Putting it all together........··.. .p17.26(346) Chapter notes and history..........···:. .p17.27(347) Exercises ················p17.28(348) Web draft2007-01-0821:59
DRAFT xii CONTENTS 16.6.3 Extractors based upon hash functions . . . . . . . . . . . . . . . . . . . . . . p16.27 (307) 16.6.4 Extractors based upon random walks on expanders . . . . . . . . . . . . . . . p16.28 (308) 16.6.5 An extractor based upon Nisan-Wigderson . . . . . . . . . . . . . . . . . . . p16.28 (308) 16.7 Applications of Extractors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p16.31 (311) 16.7.1 Graph constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p16.31 (311) 16.7.2 Running randomized algorithms using weak random sources . . . . . . . . . . p16.32 (312) 16.7.3 Recycling random bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p16.33 (313) 16.7.4 Pseudorandom generators for spacebounded computation . . . . . . . . . . . p16.33 (313) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p16.37 (317) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p16.38 (318) 17 Hardness Amplification and Error Correcting Codes p17.1 (321) 17.1 Hardness and Hardness Amplification. . . . . . . . . . . . . . . . . . . . . . . . . . . p17.1 (321) 17.2 Mild to strong hardness: Yao’s XOR Lemma. . . . . . . . . . . . . . . . . . . . . . . p17.2 (322) Proof of Yao’s XOR Lemma using Impagliazzo’s Hardcore Lemma. . . . . . . p17.3 (323) 17.3 Proof of Impagliazzo’s Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p17.4 (324) 17.4 Error correcting codes: the intuitive connection to hardness amplification . . . . . . p17.8 (328) 17.4.1 Local decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p17.10 (330) 17.5 Constructions of Error Correcting Codes . . . . . . . . . . . . . . . . . . . . . . . . . p17.12 (332) 17.5.1 Walsh-Hadamard Code. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p17.12 (332) 17.5.2 Reed-Solomon Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p17.13 (333) 17.5.3 Concatenated codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p17.14 (334) 17.5.4 Reed-Muller Codes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p17.15 (335) 17.5.5 Decoding Reed-Solomon. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p17.16 (336) Randomized interpolation: the case of ρ < 1/(d + 1) . . . . . . . . . . . . . . p17.16 (336) Berlekamp-Welch Procedure: the case of ρ < (m − d)/(2m) . . . . . . . . . . p17.16 (336) 17.5.6 Decoding concatenated codes. . . . . . . . . . . . . . . . . . . . . . . . . . . . p17.17 (337) 17.6 Local Decoding of explicit codes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p17.17 (337) 17.6.1 Local decoder for Walsh-Hadamard. . . . . . . . . . . . . . . . . . . . . . . . p17.17 (337) 17.6.2 Local decoder for Reed-Muller . . . . . . . . . . . . . . . . . . . . . . . . . . p17.18 (338) 17.6.3 Local decoding of concatenated codes. . . . . . . . . . . . . . . . . . . . . . . p17.19 (339) 17.6.4 Putting it all together. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p17.20 (340) 17.7 List decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p17.21 (341) 17.7.1 List decoding the Reed-Solomon code . . . . . . . . . . . . . . . . . . . . . . p17.22 (342) 17.8 Local list decoding: getting to BPP = P. . . . . . . . . . . . . . . . . . . . . . . . . p17.23 (343) 17.8.1 Local list decoding of the Walsh-Hadamard code. . . . . . . . . . . . . . . . . p17.24 (344) 17.8.2 Local list decoding of the Reed-Muller code . . . . . . . . . . . . . . . . . . . p17.24 (344) 17.8.3 Local list decoding of concatenated codes. . . . . . . . . . . . . . . . . . . . . p17.26 (346) 17.8.4 Putting it all together. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p17.26 (346) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p17.27 (347) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p17.28 (348) Web draft 2007-01-08 21:59
CONTENTS xiji 18 PCP and Hardness of Approximation p18.1(351) 18.1 PCP and Locally Testable Proofs ··...p18.2(352) 18.2 PCP and Hardness of Approximation p18.5(355) 18.2.1 Gap-producing reductions p18.6(356) 18.2.2 Gap problems p18.6(356) 18.2.3 Constraint Satisfaction Problems ... p18.7(357) 18.2.4 An Alternative Formulation of the PCP Theorem p18.8(358) 18.2.5 Hardness of Approximation for 3SAT and INDSET.. p18.9(359) 18.3 n--approximation of independent set is NP-hard...... p18.11(361) 18.4 NP C PCP(poly(n),1):PCP based upon Walsh-Hadamard code p18.13(363) 18.4.1 Tool:Linearity Testing and the Walsh-Hadamard Code p18.13(363) 18.4.2 Proof of Theorem18.21....................... p18.15(365) 18.4.3 PCP's of proximity p18.17(367) 18.5 Proof of the PCP Theorem.... p18.19(369) 18.5.1 Gap Amplification:Proof of Lemma 18.29. p18.21(371) 18.5.2 Alphabet Reduction:Proof of Lemma 18.30 .p18.27(377) 18.6 The original proof of the PCP Theorem. ,p18.29(379 Exercises p18.29(379) 19 More PCP Theorems and the Fourier Transform Technique p19.1(385) 19.1 Parallel Repetition of PCP's ....p19.1(385 19.2 Hastad's 3-bit PCP Theorem ... .p19.3(387) 19.3 Tool:the Fourier transform technique ,p19.4(388) 19.3.1 Fourier transform over GF(2)" p19.4(388) The connection to PCPs:High level view p19.6(390) 19.3.2 Analysis of the linearity test over GF(2)... p19.6(390) l9.3.3 Coordinate functions,Long code and its testing...·...·.· p19.7(391) 19.4 Proof of Theorem19.5.................... p19.9(393) 19.5 Learning Fourier Coefficients p19.13(397) l9.6 Other PCP Theorems:A Survey.....··. p19.14(398) 19.6.1 PCP's with sub-constant soundness parameter.... p19.14(398) 19.6.2 Amortized query complexity. 。。。。。。。 ,p19.15(399) 19.6.3 Unique games.···· p19.15(399) Exercises·········· p19.15(399) 20 Quantum Computation p20.1(401) 20.1 Quantum weirdness.······ ....p20.2(402) 20.1.1 The 2-slit experiment .p20.2(402) 20.1.2 Quantum entanglement and the Bell inequalities...... p20.3(403) 20.2 A new view of probabilistic computation............... p20.5(405) 20.3 Quantum superposition and the class BQP p20.8(408) 20.3.1 Universal quantum operations..···. p20.13(413) 20.3.2 Spooky coordination and Bell's state.·········..· p20.13(413) Wab.draft2007-01-0821:59
DRAFT CONTENTS xiii 18 PCP and Hardness of Approximation p18.1 (351) 18.1 PCP and Locally Testable Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . p18.2 (352) 18.2 PCP and Hardness of Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . p18.5 (355) 18.2.1 Gap-producing reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p18.6 (356) 18.2.2 Gap problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p18.6 (356) 18.2.3 Constraint Satisfaction Problems . . . . . . . . . . . . . . . . . . . . . . . . . p18.7 (357) 18.2.4 An Alternative Formulation of the PCP Theorem . . . . . . . . . . . . . . . p18.8 (358) 18.2.5 Hardness of Approximation for 3SAT and INDSET. . . . . . . . . . . . . . . . p18.9 (359) 18.3 n −δ -approximation of independent set is NP-hard. . . . . . . . . . . . . . . . . . . . p18.11 (361) 18.4 NP ⊆ PCP(poly(n), 1): PCP based upon Walsh-Hadamard code . . . . . . . . . . p18.13 (363) 18.4.1 Tool: Linearity Testing and the Walsh-Hadamard Code . . . . . . . . . . . . p18.13 (363) 18.4.2 Proof of Theorem 18.21 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p18.15 (365) 18.4.3 PCP’s of proximity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p18.17 (367) 18.5 Proof of the PCP Theorem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p18.19 (369) 18.5.1 Gap Amplification: Proof of Lemma 18.29 . . . . . . . . . . . . . . . . . . . . p18.21 (371) 18.5.2 Alphabet Reduction: Proof of Lemma 18.30 . . . . . . . . . . . . . . . . . . . p18.27 (377) 18.6 The original proof of the PCP Theorem. . . . . . . . . . . . . . . . . . . . . . . . . p18.29 (379) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p18.29 (379) 19 More PCP Theorems and the Fourier Transform Technique p19.1 (385) 19.1 Parallel Repetition of PCP’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p19.1 (385) 19.2 H˚astad’s 3-bit PCP Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p19.3 (387) 19.3 Tool: the Fourier transform technique . . . . . . . . . . . . . . . . . . . . . . . . . . p19.4 (388) 19.3.1 Fourier transform over GF(2)n . . . . . . . . . . . . . . . . . . . . . . . . . . p19.4 (388) The connection to PCPs: High level view . . . . . . . . . . . . . . . . . . . . p19.6 (390) 19.3.2 Analysis of the linearity test over GF(2) . . . . . . . . . . . . . . . . . . . . . p19.6 (390) 19.3.3 Coordinate functions, Long code and its testing . . . . . . . . . . . . . . . . . p19.7 (391) 19.4 Proof of Theorem 19.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p19.9 (393) 19.5 Learning Fourier Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p19.13 (397) 19.6 Other PCP Theorems: A Survey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p19.14 (398) 19.6.1 PCP’s with sub-constant soundness parameter. . . . . . . . . . . . . . . . . . p19.14 (398) 19.6.2 Amortized query complexity. . . . . . . . . . . . . . . . . . . . . . . . . . . . p19.15 (399) 19.6.3 Unique games. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p19.15 (399) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p19.15 (399) 20 Quantum Computation p20.1 (401) 20.1 Quantum weirdness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p20.2 (402) 20.1.1 The 2-slit experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p20.2 (402) 20.1.2 Quantum entanglement and the Bell inequalities. . . . . . . . . . . . . . . . . p20.3 (403) 20.2 A new view of probabilistic computation. . . . . . . . . . . . . . . . . . . . . . . . . p20.5 (405) 20.3 Quantum superposition and the class BQP . . . . . . . . . . . . . . . . . . . . . . . p20.8 (408) 20.3.1 Universal quantum operations . . . . . . . . . . . . . . . . . . . . . . . . . . . p20.13 (413) 20.3.2 Spooky coordination and Bell’s state . . . . . . . . . . . . . . . . . . . . . . . p20.13 (413) Web draft 2007-01-08 21:59
xiv CONTENTS 20.4 Quantum programmer's toolkit p20.15(415) 20.5 Grover's search algorithm.......··.··.······· p20.16(416) 20.6 Simon's Algorithm............. p20.21(421) 20.6.1 The algorithm..···.··············· p20.21(421) 20.7 Shor's algorithm:integer factorization using quantum computers. p20.22(422) 20.7.1 Quantum Fourier Transform over ZM.·....·..··. p20.23(423) Definition of the Fourier transform over ZM. p20.23(423) Fast Fourier Transform p20.24(424) Quantum Fourier transform:proof of Lemma 20.20. p20.24(424) 20.7.2 The Order-Finding Algorithm............. p20.25(425) Analysis:the case that rM.... p20.26(426) The case that r M p20.26(426) 20.7.3 Reducing factoring to order finding. p20.28(428) 20.8 BQP and classical complexity classes .... p20.29(429) Chapter notes and history..,.·········· .p20.29(429 Exercises p20.31(431) 20.A Rational approximation of real numbers ............. p20.32(432) 21 Logic in complexity theory p21.1(433) 21.1 Logical definitions of complexity classes... ····p21.2(434) 21.1.1 Fagin's definition of NP p21.2(434) 21.1.2 MAX-SNP .p21.3(435) 21.2 Proof complexity as an approach to NP versus coNP p21.3(435) 21.2.1 Resolution..················· p21.3(435) 21.2.2 Frege Systems 。 p21.4(436) 21.2.3 Polynomial calculus p21.4(436) 21.3 Is P NP unproveable? p21.4(436) 22 Why are circuit lowerbounds so difficult? p22.1(437) 22.1 Formal Complexity Measures....... ····.p22.1(437) 22.2 Natural Properties ... p22.3(439) 22.3 Limitations of Natural Proofs p22.5(441) 22.4 My personal view.······· p22.6(442) Exercises··········· p22.7(443) Chapter notes and history .p22.7(443) Appendices p22.9(445) A Mathematical Background. pA.1(447) A.1 Mathematical Proofs..··· .....pA.1(447） A.2Sets,Functions,.Pairs,Strings,Graphs,Logic.·......·...·. ...·.pA.3(449) A.3 Probability theory...................··.....·..·.......pA.4(450) A.3.1 Random variables and expectations..·······················pA.5(451) Web draft2007-01-0821:59
DRAFT xiv CONTENTS 20.4 Quantum programmer’s toolkit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p20.15 (415) 20.5 Grover’s search algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p20.16 (416) 20.6 Simon’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p20.21 (421) 20.6.1 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p20.21 (421) 20.7 Shor’s algorithm: integer factorization using quantum computers. . . . . . . . . . . . p20.22 (422) 20.7.1 Quantum Fourier Transform over ZM. . . . . . . . . . . . . . . . . . . . . . . p20.23 (423) Definition of the Fourier transform over ZM. . . . . . . . . . . . . . . . . . . p20.23 (423) Fast Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p20.24 (424) Quantum Fourier transform: proof of Lemma 20.20 . . . . . . . . . . . . . . . p20.24 (424) 20.7.2 The Order-Finding Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . p20.25 (425) Analysis: the case that r|M . . . . . . . . . . . . . . . . . . . . . . . . . . . . p20.26 (426) The case that r 6 |M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p20.26 (426) 20.7.3 Reducing factoring to order finding. . . . . . . . . . . . . . . . . . . . . . . . p20.28 (428) 20.8 BQP and classical complexity classes . . . . . . . . . . . . . . . . . . . . . . . . . . p20.29 (429) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p20.29 (429) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p20.31 (431) 20.A Rational approximation of real numbers . . . . . . . . . . . . . . . . . . . . . . . . . p20.32 (432) 21 Logic in complexity theory p21.1 (433) 21.1 Logical definitions of complexity classes . . . . . . . . . . . . . . . . . . . . . . . . . p21.2 (434) 21.1.1 Fagin’s definition of NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p21.2 (434) 21.1.2 MAX-SNP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p21.3 (435) 21.2 Proof complexity as an approach to NP versus coNP . . . . . . . . . . . . . . . . . p21.3 (435) 21.2.1 Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p21.3 (435) 21.2.2 Frege Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p21.4 (436) 21.2.3 Polynomial calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p21.4 (436) 21.3 Is P 6= NP unproveable? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p21.4 (436) 22 Why are circuit lowerbounds so difficult? p22.1 (437) 22.1 Formal Complexity Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p22.1 (437) 22.2 Natural Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p22.3 (439) 22.3 Limitations of Natural Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p22.5 (441) 22.4 My personal view . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p22.6 (442) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p22.7 (443) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p22.7 (443) Appendices p22.9 (445) A Mathematical Background. pA.1 (447) A.1 Mathematical Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . pA.1 (447) A.2 Sets, Functions, Pairs, Strings, Graphs, Logic. . . . . . . . . . . . . . . . . . . . . . . pA.3 (449) A.3 Probability theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . pA.4 (450) A.3.1 Random variables and expectations. . . . . . . . . . . . . . . . . . . . . . . . pA.5 (451) Web draft 2007-01-08 21:59
CONTENTS XV A.3.2 The averaging argument ···············.pA.6(452) A.3.3 Conditional probability and independence ................... pA.7(453) A.3.4 Deviation upperbounds pA.7(453) A.3.5 Some other inequalities......··.······.········ pA.9(455) Jensen's inequality..························ pA.9(455) Approximating the binomial coefficient............... pA.9(455) More useful estimates....··················· pA.10(456) A.4 Finite fields and groups pA.10(456) A.4.1 Non-prime fields. ·pA.11(457) A.4.2 Groups...········ .pA.11(457) A.5 Vector spaces and Hilbert spaces pA.12(458) A.6 Polynomials..··.······· ..pA.12(458) Web draft2007-01-0821:59
DRAFT CONTENTS xv A.3.2 The averaging argument . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . pA.6 (452) A.3.3 Conditional probability and independence . . . . . . . . . . . . . . . . . . . . pA.7 (453) A.3.4 Deviation upperbounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . pA.7 (453) A.3.5 Some other inequalities. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . pA.9 (455) Jensen’s inequality. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . pA.9 (455) Approximating the binomial coefficient . . . . . . . . . . . . . . . . . . . . . . pA.9 (455) More useful estimates. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . pA.10 (456) A.4 Finite fields and groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . pA.10 (456) A.4.1 Non-prime fields. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . pA.11 (457) A.4.2 Groups. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . pA.11 (457) A.5 Vector spaces and Hilbert spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . pA.12 (458) A.6 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . pA.12 (458) Web draft 2007-01-08 21:59
Introduction "As long as a branch of science offers an abundance of problems,so long it is alive; a lack of problems foreshadows extinction or the cessation of independent develop- ment.” David Hilbert,1900 "The subject of my talk is perhaps most directly indicated by simply asking two ques- tions:first,is it harder to multiply than to add?and second,why?...I (would like to)show that there is no algorithm for multiplication computationally as simple as that for addition,and this proves something of a stumbling block." Alan Cobham,1964 [Cob64] The notion of computation has existed in some form for thousands of years.In its everyday meaning,this term refers to the process of producing an output from a set of inputs in a finite number of steps.Here are three examples for computational tasks: Given two integer numbers,compute their product. Given a set of n linear equations over n variables,find a solution if it exists. Given a list of acquaintances and a list of containing all pairs of individuals who are not on speaking terms with each other,find the largest set of acquaintances you can invite to a dinner party such that you do not invite any two who are not on speaking terms. In the first half of the 20th century,the notion of "computation"was made much more precise than the hitherto informal notion of "a person writing numbers on a note pad following certain rules."Many different models of computation were discovered-Turing machines,lambda calculus, cellular automata,pointer machines,bouncing billiards balls,Conway's Game of life,etc.-and found to be equivalent.More importantly,they are all universal,which means that each is capable of implementing all computations that we can conceive of on any other model (see Chapter 1).The notion of universality motivated the invention of the standard electronic computer,which is capable of executing all possible programs.The computer's rapid adoption in society in the subsequent half decade brought computation into every aspect of modern life,and made computational issues important in design,planning,engineering,scientific discovery,and many other human endeavors. However,computation is not just a practical tool,but also a major scientific concept.General- izing from models such as cellular automata,scientists have come to view many natural phenomena Web draft2007-01-0821:59 p0.1(1) Complexity Theory:A Modern Approach.C2006 Sanjeev Arora and Boaz Barak.References and attributions are still incomplete
DRAFT Introduction “As long as a branch of science offers an abundance of problems, so long it is alive; a lack of problems foreshadows extinction or the cessation of independent development.” David Hilbert, 1900 “The subject of my talk is perhaps most directly indicated by simply asking two questions: first, is it harder to multiply than to add? and second, why?...I (would like to) show that there is no algorithm for multiplication computationally as simple as that for addition, and this proves something of a stumbling block.” Alan Cobham, 1964 [Cob64] The notion of computation has existed in some form for thousands of years. In its everyday meaning, this term refers to the process of producing an output from a set of inputs in a finite number of steps. Here are three examples for computational tasks: • Given two integer numbers, compute their product. • Given a set of n linear equations over n variables, find a solution if it exists. • Given a list of acquaintances and a list of containing all pairs of individuals who are not on speaking terms with each other, find the largest set of acquaintances you can invite to a dinner party such that you do not invite any two who are not on speaking terms. In the first half of the 20th century, the notion of “computation” was made much more precise than the hitherto informal notion of “a person writing numbers on a note pad following certain rules.” Many different models of computation were discovered —Turing machines, lambda calculus, cellular automata, pointer machines, bouncing billiards balls, Conway’s Game of life, etc.— and found to be equivalent. More importantly, they are all universal, which means that each is capable of implementing all computations that we can conceive of on any other model (see Chapter 1). The notion of universality motivated the invention of the standard electronic computer, which is capable of executing all possible programs. The computer’s rapid adoption in society in the subsequent half decade brought computation into every aspect of modern life, and made computational issues important in design, planning, engineering, scientific discovery, and many other human endeavors. However, computation is not just a practical tool, but also a major scientific concept. Generalizing from models such as cellular automata, scientists have come to view many natural phenomena Web draft 2007-01-08 21:59 Complexity Theory: A Modern Approach. © 2006 Sanjeev Arora and Boaz Barak. References and attributions are still incomplete. p0.1 (1)