Lecture notes on Algorithm analysis and Computational complexity

how to calculate computational complexity and how to express computational complexity pdf free downlaod
NathanBenett Profile Pic
NathanBenett,Germany,Researcher
Published Date:11-07-2017
Your Website URL(Optional)
Comment
i Computational Complexity: A Modern Approach Draft of a book: Dated January 2007 Comments welcome Sanjeev Arora and Boaz Barak Princeton University complexitybookgmail.com Not to be reproduced or distributed without the authors’ permission This is an Internet draft. Some chapters are more finished than others. References and attributions are very preliminary and we apologize in advance for any omissions (but hope you will nevertheless point them out to us). Please send us bugs, typos, missing references or general comments to complexitybookgmail.com — Thank You DRAFTvi CONTENTS 2.3 The Cook-Levin Theorem: Computation is Local . . . . . . . . . . . . . . . . . . . . p2.6(44) 2.3.1 Boolean formulae and the CNF form. . . . . . . . . . . . . . . . . . . . . . . p2.7(45) 2.3.2 The Cook-Levin Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p2.7(45) 2.3.3 Warmup: Expressiveness of boolean formulae . . . . . . . . . . . . . . . . . . p2.8(46) 2.3.4 Proof of Lemma 2.12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p2.9(47) 2.3.5 Reducing SAT to 3SAT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p2.11(49) 2.3.6 More thoughts on the Cook-Levin theorem . . . . . . . . . . . . . . . . . . . p2.11(49) 2.4 The web of reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p2.12(50) In praise of reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p2.16(54) Coping with NP hardness. . . . . . . . . . . . . . . . . . . . . . . . . . . . . p2.16(54) 2.5 Decision versus search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p2.17(55) 2.6 coNP, EXP and NEXP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p2.18(56) 2.6.1 coNP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p2.18(56) 2.6.2 EXP and NEXP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p2.19(57) 2.7 More thoughts about P, NP, and all that . . . . . . . . . . . . . . . . . . . . . . . . p2.20(58) 2.7.1 The philosophical importance of NP . . . . . . . . . . . . . . . . . . . . . . . p2.20(58) 2.7.2 NP and mathematical proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . p2.20(58) 2.7.3 What if P=NP? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p2.21(59) 2.7.4 What if NP=coNP? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p2.21(59) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p2.22(60) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p2.23(61) 3 Diagonalization p3.1 (65) 3.1 Time Hierarchy Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p3.2(66) 3.2 Space Hierarchy Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p3.2(66) 3.3 Nondeterministic Time Hierarchy Theorem . . . . . . . . . . . . . . . . . . . . . . . p3.3(67) 3.4 Ladner’s Theorem: Existence of NP-intermediate problems. . . . . . . . . . . . . . . p3.4(68) 3.5 Oracle machines and the limits of diagonalization? . . . . . . . . . . . . . . . . . . . p3.6(70) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p3.8(72) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p3.9(73) 4 Space complexity p4.1 (75) 4.1 Configuration graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p4.2(76) 4.2 Some space complexity classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p4.4(78) 4.3 PSPACE completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p4.5(79) 4.3.1 Savitch’s theorem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p4.8(82) 4.3.2 The essence of PSPACE: optimum strategies for game-playing. . . . . . . . p4.8(82) 4.4 NL completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p4.10(84) 4.4.1 Certificate definition of NL: read-once certificates . . . . . . . . . . . . . . . p4.12(86) 4.4.2 NL=coNL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p4.13(87) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p4.14(88) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p4.14(88) Web draft 2007-01-08 21:59 DRAFTCONTENTS vii 5 The Polynomial Hierarchy and Alternations p5.1 (91) p p 5.1 The classes Σ and Π . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p5.1(91) 2 2 5.2 The polynomial hierarchy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p5.3(93) 5.2.1 Properties of the polynomial hierarchy.. . . . . . . . . . . . . . . . . . . . . . p5.3(93) 5.2.2 Complete problems for levels of PH . . . . . . . . . . . . . . . . . . . . . . . p5.4(94) 5.3 Alternating Turing machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p5.5(95) 5.3.1 Unlimited number of alternations? . . . . . . . . . . . . . . . . . . . . . . . . p5.6(96) 5.4 Time versus alternations: time-space tradeoffs for SAT.. . . . . . . . . . . . . . . . . p5.6(96) 5.5 Defining the hierarchy via oracle machines. . . . . . . . . . . . . . . . . . . . . . . . p5.8(98) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p5.9(99) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p5.10(100) 6 Circuits p6.1 (101) 6.1 Boolean circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p6.1(101) 6.1.1 Turing machines that take advice . . . . . . . . . . . . . . . . . . . . . . . . . p6.5(105) 6.2 Karp-Lipton Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p6.6(106) 6.3 Circuit lowerbounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p6.7(107) 6.4 Non-uniform hierarchy theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p6.8(108) 6.5 Finer gradations among circuit classes . . . . . . . . . . . . . . . . . . . . . . . . . . p6.8(108) 6.5.1 Parallel computation and NC . . . . . . . . . . . . . . . . . . . . . . . . . . . p6.9(109) 6.5.2 P-completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p6.10(110) 6.6 Circuits of exponential size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p6.11(111) 6.7 Circuit Satisfiability and an alternative proof of the Cook-Levin Theorem . . . . . . p6.12(112) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p6.13(113) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p6.13(113) 7 Randomized Computation p7.1 (115) 7.1 Probabilistic Turing machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.2(116) 7.2 Some examples of PTMs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.3(117) 7.2.1 Probabilistic Primality Testing . . . . . . . . . . . . . . . . . . . . . . . . . . p7.3(117) 7.2.2 Polynomial identity testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.4(118) 7.2.3 Testing for perfect matching in a bipartite graph. . . . . . . . . . . . . . . . . p7.5(119) 7.3 One-sided and zero-sided error: RP, coRP, ZPP . . . . . . . . . . . . . . . . . . . p7.6(120) 7.4 The robustness of our definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.7(121) 7.4.1 Role of precise constants, error reduction. . . . . . . . . . . . . . . . . . . . . p7.7(121) 7.4.2 Expected running time versus worst-case running time. . . . . . . . . . . . . p7.10(124) 7.4.3 Allowing more general random choices than a fair random coin. . . . . . . . . p7.10(124) 7.5 Randomness efficient error reduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.11(125) 7.6 BPP⊆P/poly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.12(126) 7.7 BPP is in PH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.13(127) 7.8 State of our knowledge about BPP. . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.14(128) Complete problems for BPP? . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.14(128) Does BPTIME have a hierarchy theorem? . . . . . . . . . . . . . . . . . . . p7.15(129) Web draft 2007-01-08 21:59 DRAFTviii CONTENTS 7.9 Randomized reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.15(129) 7.10 Randomized space-bounded computation . . . . . . . . . . . . . . . . . . . . . . . . p7.15(129) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.17(131) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.18(132) 7.A Random walks and eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.21(135) 7.A.1 Distributions as vectors and the parameter λ(G). . . . . . . . . . . . . . . . . p7.21(135) 7.A.2 Analysis of the randomized algorithm for undirected connectivity. . . . . . . p7.24(138) 7.B Expander graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.25(139) 7.B.1 The Algebraic Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p7.25(139) 7.B.2 Combinatorial expansion and existence of expanders. . . . . . . . . . . . . . . p7.27(141) 7.B.3 Error reduction using expanders. . . . . . . . . . . . . . . . . . . . . . . . . . p7.29(143) 8 Interactive proofs p8.1 (147) 8.1 Warmup: Interactive proofs with a deterministic verifier . . . . . . . . . . . . . . . . p8.1(147) 8.2 The class IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.3(149) 8.3 Proving that graphs are not isomorphic. . . . . . . . . . . . . . . . . . . . . . . . . . p8.4(150) 8.4 Public coins and AM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.5(151) 8.4.1 Set Lower Bound Protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.6(152) Tool: Pairwise independent hash functions. . . . . . . . . . . . . . . . . . . . p8.7(153) The lower-bound protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.9(155) 8.4.2 Some properties of IP and AM. . . . . . . . . . . . . . . . . . . . . . . . . . p8.10(156) 8.4.3 Can GI be NP-complete? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.11(157) 8.5 IP=PSPACE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.11(157) 8.5.1 Arithmetization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.12(158) 8.5.2 Interactive protocol for SAT . . . . . . . . . . . . . . . . . . . . . . . . . . p8.12(158) D Sumcheck protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.13(159) 8.5.3 Protocol for TQBF: proof of Theorem 8.17 . . . . . . . . . . . . . . . . . . . p8.14(160) 8.6 The power of the prover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.15(161) 8.7 Program Checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.16(162) 8.7.1 Languages that have checkers . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.17(163) 8.8 Multiprover interactive proofs (MIP) . . . . . . . . . . . . . . . . . . . . . . . . . . p8.18(164) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.19(165) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.20(166) 8.A Interactive proof for the Permanent . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.21(167) 8.A.1 The protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p8.23(169) 9 Complexity of counting p9.1 (171) 9.1 The class P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p9.2(172) 9.1.1 The class PP: decision-problem analog for P. . . . . . . . . . . . . . . . . . p9.3(173) 9.2 P completeness. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p9.4(174) 9.2.1 Permanent and Valiant’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . p9.4(174) 9.2.2 Approximate solutions to P problems . . . . . . . . . . . . . . . . . . . . . p9.8(178) SAT 9.3 Toda’s Theorem: PH⊆P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p9.9(179) Web draft 2007-01-08 21:59 DRAFTCONTENTS ix 9.3.1 The class⊕P and hardness of satisfiability with unique solutions. . . . . . . p9.9(179) Proof of Theorem 9.15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p9.11(181) 9.3.2 Step 1: Randomized reduction from PH to⊕P . . . . . . . . . . . . . . . . . p9.11(181) 9.3.3 Step 2: Making the reduction deterministic . . . . . . . . . . . . . . . . . . . p9.13(183) 9.4 Open Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p9.14(184) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p9.14(184) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p9.15(185) 10 Cryptography p10.1 (187) 10.1 Hard-on-average problems and one-way functions . . . . . . . . . . . . . . . . . . . . p10.2(188) 10.1.1 Discussion of the definition of one-way function . . . . . . . . . . . . . . . . . p10.4(190) 10.1.2 Random self-reducibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p10.5(191) 10.2 What is a random-enough string? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p10.5(191) 10.2.1 Blum-Micali and Yao definitions . . . . . . . . . . . . . . . . . . . . . . . . . p10.6(192) 10.2.2 Equivalence of the two definitions. . . . . . . . . . . . . . . . . . . . . . . . . p10.8(194) 10.3 One-way functions and pseudorandom number generators . . . . . . . . . . . . . . . p10.10(196) 10.3.1 Goldreich-Levin hardcore bit . . . . . . . . . . . . . . . . . . . . . . . . . . . p10.10(196) 10.3.2 Pseudorandom number generation . . . . . . . . . . . . . . . . . . . . . . . . p10.13(199) 10.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p10.13(199) 10.4.1 Pseudorandom functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p10.13(199) 10.4.2 Private-key encryption: definition of security . . . . . . . . . . . . . . . . . . p10.14(200) 10.4.3 Derandomization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p10.15(201) 10.4.4 Tossing coins over the phone and bit commitment . . . . . . . . . . . . . . . p10.16(202) 10.4.5 Secure multiparty computations . . . . . . . . . . . . . . . . . . . . . . . . . p10.16(202) 10.4.6 Lowerbounds for machine learning . . . . . . . . . . . . . . . . . . . . . . . . p10.17(203) 10.5 Recent developments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p10.17(203) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p10.17(203) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p10.18(204) II Lowerbounds for Concrete Computational Models p10.21 (207) 11 Decision Trees p11.2 (211) 11.1 Certificate Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p11.4(213) 11.2 Randomized Decision Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p11.6(215) 11.3 Lowerbounds on Randomized Complexity . . . . . . . . . . . . . . . . . . . . . . . . p11.6(215) 11.4 Some techniques for decision tree lowerbounds. . . . . . . . . . . . . . . . . . . . . . p11.8(217) 11.5 Comparison trees and sorting lowerbounds . . . . . . . . . . . . . . . . . . . . . . . . p11.9(218) 11.6 Yao’s MinMax Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p11.9(218) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p11.9(218) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p11.10(219) Web draft 2007-01-08 21:59 DRAFTCONTENTS 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 DRAFTxvi CONTENTS Web draft 2007-01-08 21:59 DRAFTIntroduction “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.” Manydifferentmodelsofcomputationwerediscovered—Turingmachines,lambdacalculus, 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 ofimplementingallcomputations thatwe canconceiveofonanyothermodel(see Chapter1). The notionofuniversalitymotivatedtheinventionofthestandardelectronic computer,whichiscapable 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, computationisnotjustapracticaltool, butalsoamajorscientificconcept. General- izingfrommodelssuchascellularautomata, scientistshavecometoviewmanynaturalphenomena Web draft 2007-01-08 21:59 p0.1 (1) Complexity Theory: A Modern Approach.© 2006 Sanjeev Arora and Boaz Barak. References and attributions are still incomplete. DRAFTp0.2 (2) CONTENTS as akin to computational processes. The understanding of reproduction in living things was trig- gered by the discovery of self-reproduction in computational machines. (In fact, a famous article by Pauli predicted the existence of a DNA-like substance in cells almost a decade before Watson and Crick discovered it.) Today, computational models underlie many research areas in biology and neuroscience. Several physics theories such as QED give a description of nature that is very reminiscent of computation, motivating some scientists to even suggest that the entire universe may be viewed as a giant computer (see Lloyd ?). In an interesting twist, such physical theories have been used in the past decade to design a model for quantum computation; see Chapter 20. From 1930s to the 1950s, researchers focused on the theory of computability and showed that several interesting computational tasks are inherently uncomputable: no computer can solve them without going into infinite loops (i.e., never halting) on certain inputs. Though a beautiful theory, it will not be our focus here. (But, see the texts SIP96, HMU01, Koz97,?.) Instead, we focus on issues of computational efficiency. Computational complexity theory is concerned with how much computational resources are required to solve a given task. The questions it studies include the following: 1. Many computational tasks involve searching for a solution across a vast space of possibilities (for example, the aforementioned tasks of solving linear equations and finding a maximal set of invitees to a dinner party). Is there an efficient search algorithm for all such tasks, or do some tasks inherently require an exhaustive search? As we will see in Chapter 2, this is the famous “P vs. NP” question that is considered the central problem of complexity theory. Computational search tasks of the form above arise in a host of disciplines including the life sciences, social sciences and operations research, and computational complexity has provided strong evidence that many of these tasks are inherently intractable. 2. Can algorithms use randomness (i.e., coin tossing) to speed up computation? Chapter 7 presents probabilistic algorithms and shows several algorithms and techniques that use probability to solve tasks more efficiently. But Chapters 16 and 17 show a surprising recent result giving strong evidence that randomness does not help speed up computation, in the sense that any probabilistic algorithm can be replaced with a deterministic algorithm (tossing no coins) that is almost as efficient. 3. Can hard problems be solved quicker if we allow the algorithms to err on a small number of inputs, or to only compute an approximate solution? Average-case complexity and approximation algorithms are studied in Chapters 15, 17, 18 and 19. These chapters also show fascinating connections between these questions, the power of randomness, different notions of mathematical proofs, and the theory of error correcting codes. 4. Is there any use for computationally hard problems? For example, can we use them to construct secret codes that are unbreakable? (at least in the universe’s lifetime). Our society increasingly relies on digital cryptography for commerce and security. As de- scribed in Chapter 10, these secret codes are built using certain hard computational tasks Web draft 2007-01-08 21:59 DRAFTCONTENTS p0.3 (3) such as factoring integers. The security of digital cryptography is intimately related to theP vs. NP question (see Chapter 2) and average-case complexity (see Chapters 15). 5. Can we use the counterintuitive quantum mechanical properties of our universe to solve hard problems faster? Chapter20describesthefascinatingnotionofquantum computers thatusesuchpropertiesto speed up certain computations. Although there are many theoretical and practical obstacles toactuallybuildingsuchcomputers, theyhavegeneratedtremendousinterestinrecentyears. ThisisnotleastduetoShor’salgorithmthatshowedthat,ifbuilt,quantumcomputerswillbe able to factor integers efficiently. (Thus breaking many of the currently used cryptosystems.) 6. Can we generate mathematical proofs automatically? Can we check a mathematical proof by only reading 3 probabilistically chosen letters from it? Do interactive proofs, involving a dialog between prover and verifier, have more power than standard “static” mathematical proofs? The notion of proof, central to mathematics, turns out to be central to computational com- plexity as well, and complexity has shed new light on the meaning of mathematical proofs. Whether mathematical proofs can be generated automatically turns out to depend on the P vs. NP question (see Chapter 2). Chapter 18 describes probabilistically checkable proofs. These are surprisingly robust mathematical proofs that can checked by only reading them in very few probabilistically chosen locations. Interactive proofs are studied in Chapter 8. Fi- nally, proof complexity, a subfield of complexity studying the minimal proof length of various statements, is studied in Chapter 21. At roughly 40 years of age, Complexity theory is still an infant science. Thus we still do not have complete answers for any of these questions. (In a surprising twist, computational complexity has also been used to provide evidence for the hardness to solve some of the questions of ... computational complexity; see Chapter 22.) Furthermore, many major insights on these questions were only found in recent years. Meaning of efficiency Now we explain the notion of computational efficiency, using the three examples for computational tasks we mentioned above. We start with the task of multiplying two integers. Consider two different methods (or algorithms) to perform this task. The first is repeated addition: to compute a·b, just adda to itselfb−1 times. The other is the grade-school algorithm illustrated in Figure 1. Though the repeated addition algorithm is perhaps simpler than the grade-school algorithm, we somehow feel that the latter is better. Indeed, it is much more efficient. For example, multiplying 577 by 423 using repeated addition requires 422 additions, whereas doing it with the grade-school algorithm requires only 3 additions and 3 multiplications of a number by a single digit. We will quantify the efficiency of an algorithm by studying the number of basic operations it performsasthesizeoftheinputincreases. Here,thebasicoperations areadditionandmultiplication of single digits. (In other settings, we may wish to throw in division as a basic operation.) The Web draft 2007-01-08 21:59 DRAFTp0.4 (4) CONTENTS 5 7 7 4 2 3 1 7 3 1 1 1 5 4 2 3 0 8 2 4 4 0 7 1 Figure 1: Grade-school algorithm for multiplication. Illustrated for computing 577·423. size of the input is the number of digits in the numbers. The number of basic operations used to n−1 n 2 multiply two n-digit numbers (i.e., numbers between 10 and 10 ) is at most 2n for the grade- n−1 school algorithm and at least n10 for repeated addition. Phrased this way, the huge difference betweenthetwoalgorithmsisapparent: evenfor11-digitnumbers, apocketcalculatorrunningthe grade-school algorithm would beat the best current supercomputer running the repeated addition algorithm. For slightly larger numbers even a fifth grader with pen and paper would outperform a supercomputer. We see that the efficiency of an algorithm is to a considerable extent much more important than the technology used to execute it. Surprisingly enough, there is an even faster algorithm for multiplication that uses the Fast Fourier Transform. It was only discovered some 40 years ago and multiplies two n-digit numbers using cnlogn operations where c is some absolute constant independent of n. (Using asymptotic notation, we call this an O(nlogn)-step algorithm; see Chapter 1.) Similarly, for the task of solving linear equations, the classic Gaussian elimination algorithm (namedafterGaussbutalreadyknowninsomeformtoChinesemathematiciansofthefirstcentury) 3 uses O(n ) basic arithmetic operations to solve n equations over n variables. In the late 1960’s, 2.81 StrassenfoundamoreefficientalgorithmthatusesroughlyO(n )operations,andthebestcurrent 2.376 algorithm takes O(n ) operations. The dinner party task also has an interesting story. As in the case of multiplication, there is an obvious and simple inefficient algorithm: try all possible subsets of the n people from the largest to the smallest, and stop when you find a subset that does not include any pair of guests who are not on speaking terms. This algorithm can take as much time as the number of subsets of a n group ofn people, which is 2 . This is highly unpractical —an organizer of, say, a 70-person party, would need to plan it at least a thousand years in advance, even if she has a supercomputer at her disposal. Surprisingly, we still do not know of a significantly better algorithm. In fact, as we will see in Chapter 2, we have reasons to suspect that no efficient algorithm exists for this task. We will see that it is equivalent to the independent set computational problem, which, together with thousands of other important problems, is NP-complete. The famous “P versus NP” question asks whether or not any of these problems has an efficient algorithm. Proving nonexistence of efficient algorithms We have seen that sometimes computational tasks have nonintuitive algorithms that are more efficient than algorithms that were known for thousands of years. It would therefore be really Web draft 2007-01-08 21:59 DRAFTCONTENTS p0.5 (5) interesting to prove for some computational tasks that the current algorithm is the best —in other words, no better algorithms exist. For instance, we could try to prove that the O(nlogn)-step algorithm for multiplication can never be improved (thus implying that multiplication is inherently more difficult than addition, which does have an O(n)-step algorithm). Or, we could try to prove n/10 that there is no algorithm for the dinner party task that takes fewer than 2 steps. Since we cannot very well check every one of the infinitely many possible algorithms, the only waytoverifythatthecurrentalgorithmisthebestistomathematically prove thatthereisnobetter algorithm. This may indeed be possible to do, since computation can be given a mathematically precise model. There are several precedents for proving impossibility results in mathematics, such as the independence of Euclid’s parallel postulate from the other basic axioms of geometry, or the impossibility of trisecting an arbitrary angle using a compass and straightedge. Such results count among the most interesting, fruitful, and surprising results in mathematics. Given the above discussion, it is no surprise that mathematical proofs are the main tool of complexity theory, and that this book is filled with theorems, definitions and lemmas. However, we hardly use any fancy mathematics and so the main prerequisite for this book is the ability to read (and perhaps even enjoy) mathematical proofs. The reader might want to take a quick look at Appendix A, that reviews mathematical proofs and other notions used, and come back to it as needed. We conclude with another quote from Hilbert’s 1900 lecture: Proofs of impossibility were effected by the ancients ... and in later mathematics, the question as to the impossibility of certain solutions plays a preminent part. ... In other sciences also one meets old problems which have been settled in a manner most satisfactory and most useful to science by the proof of their impossibility. ... After seeking in vain for the construction of a perpetual motion machine, the relations were investigated which must subsist between the forces of nature if such a machine is to be impossible; and this inverted question led to the discovery of the law of the conservation of energy. ... It is probably this important fact along with other philosophical reasons that gives rise to conviction ... that every definite mathematical problem must necessary be susceptible of an exact settlement, either in the form of an actual answer to the question asked, or by the proof of the impossibility of its solution and therewith the necessary failure of all attempts. ... This conviction... is a powerful incentive to the worker. We hear within us the perpetual call: There is the problem. Seek its solution. You can find it by pure reason, for in mathematics there is no ignorabimus. Web draft 2007-01-08 21:59 DRAFTp0.6 (6) CONTENTS Web draft 2007-01-08 21:59 DRAFTCONTENTS p0.7 (7) Conventions: A whole number is a number in the setZ =0,±1,±2,.... A number denoted by one of the letters i,j,k,`,m,n is always assumed to be whole. If n≥ 1, then we denote by n the set1,...,n. For a real numberx, we denote bydxe the smallestn∈Z such thatn≥x and bybxc the largest n∈Z such that n≤x. Whenever we use a real number in a context requiring a whole number, the operatord e is implied. We denote by logx the logarithm ofx to the base 2. Wesaythataconditionholdsfor sufficiently largenifitholdsforeveryn≥N forsomenumberN P n 2 (for example, 2 100n for sufficiently large n). We use expressions such as f(i) (as opposed i P n to, say, f(i)) when the range of values i takes is obvious from the context. If u is a string or i=1 th vector, then u denotes the value of the i symbol/coordinate of u. i Web draft 2007-01-08 21:59 DRAFTp0.8 (8) CONTENTS Web draft 2007-01-08 21:59 DRAFTPart I Basic Complexity Classes Web draft 2007-01-08 21:59 p0.9 (9) Complexity Theory: A Modern Approach.© 2006 Sanjeev Arora and Boaz Barak. References and attributions are still incomplete. DRAFTDRAFTChapter 1 The computational model —and why it doesn’t matter “The idea behind digital computers may be explained by saying that these machines are intended to carry out any operations which could be done by a human computer. The human computer is supposed to be following fixed rules; he has no authority to deviate from them in any detail. We may suppose that these rules are supplied in a book, which is altered whenever he is put on to a new job. He has also an unlimited supply of paper on which he does his calculations.” Alan Turing, 1950 “Turing has for the first time succeeded in giving an absolute definition of an in- teresting epistemological notion, i.e., one not depending on the formalism chosen.” Kurt G¨odel, 1946 The previous chapter gave an informal introduction to computation and efficient computations in context of arithmetic. IN this chapter we show a more rigorous and general definition. As mentioned earlier, one of the surprising discoveries of the 1930s was that all known computational modelsareableto simulate eachother. Thusthesetof computableproblemsdoesnotdependupon the computational model. In this book we are interested in issues of computational efficiency, and therefore in classes of “efficiently computable” problems. Here, at first glance, it seems that we have to be very careful aboutourchoiceofacomputationalmodel, sinceevenakidknowsthatwhetherornotanewvideo game program is “efficiently computable” depends upon his computer’s hardware. Surprisingly though, we can restrict attention to a single abstract computational model for studying many questions about efficiency—the Turing machine. The reason is that the Turing Machine seems able to simulate all physically realizable computational models with very little loss of efficiency. Thus the set of “efficiently computable” problems is at least as large for the Turing Machine as for any other model. (One possible exception is the quantum computer model, but we do not currently know if it is physically realizable.) Web draft 2007-01-08 21:59 p1.1 (11) Complexity Theory: A Modern Approach.© 2006 Sanjeev Arora and Boaz Barak. References and attributions are still incomplete. DRAFTp1.2 (12) 1.1. ENCODINGS AND LANGUAGES: SOME CONVENTIONS The Turing machine is a simple embodiment of the age-old intuition that computation consists of applying mechanical rules to manipulate numbers, where the person/machine doing the manip- ulation is allowed a scratch pad on which to write the intermediate results. The Turing Machine can be also viewed as the equivalent of any modern programming language — albeit one with no 1 built-in prohibition about memory size . In fact, this intuitive understanding of computation will suffice for most of the book and most readers can skip many details of the model on a first reading, returning to them later as needed. The rest of the chapter formally defines the Turing Machine and the notion of running time, whichisonemeasureofcomputationaleffort. Italsopresentstheimportantnotionofthe universal Turing machine. Section1.5introducesaclassof“efficientlycomputable”problemscalledP(which stands for Polynomial time) and discuss its philosophical significance. The section also points out how throughout the book the definition of the Turing Machine and the class P will be a starting point for definitions of many other models, including nondeterministic, probabilistic and quantum Turing machines, Boolean circuits, parallel computers, decision trees, and communication games. Some of these models are introduced to study arguably realizable modes of physical computation, while others are mainly used to gain insights on Turing machines. 1.1 Encodings and Languages: Some conventions Below we specify some of the notations and conventions used throughout this chapter and this book to represent computational problem. We make use of some notions from discrete math such as strings, sets, functions, tuples, and graphs. All of these notions are reviewed in Appendix ??. 1.1.1 Representing objects as strings In general we study the complexity of computing a function whose input and output are finite strings of bits. (A string of bits is a finite sequence of zeroes and ones. The set of all strings of n ∗ n length n is denoted by0,1 , while the set of all strings is denoted by0,1 =∪ 0,1 ; see n≥0 Appendix A.) Note that simple encodings can be used to represent general objects—integers, pairs of integers, graphs, vectors, matrices, etc.— as strings of bits. For example, we can represent an integer as a string using the binary expansion (e.g., 34 is represented as 100010) and a graph as its adjacency matrix (i.e., an n vertex graph G is represented by an n×n 0/1-valued matrix A such thatA =1 iff the edge (i,j) is present inG). We will typically avoid dealing explicitly with i,j such low level issues of representation, and will use x to denote some canonical (and unspecified) x y binary representation of the object x. Often we will drop the symbols and simply use x to xy denote both the object and its representation. Representingpairsandtuples. Weusethenotationhx,yitodenotetheorderedpairconsisting of x and y. A canonical representation forhx,yi can be easily obtained from the representations of x and y. For example, we can first encodehx,yi as the string x ◦◦ y over the alphabet x y xy 1 Though the assumption of an infinite memory may seem unrealistic at first, in the complexity setting it is of no consequence since we will restrict the machine to use a finite amount of tape cells for any given input (the number allowed will depend upon the input size). Web draft 2007-01-08 21:59 DRAFT1.1. ENCODINGS AND LANGUAGES: SOME CONVENTIONS p1.3 (13) 0,1, (where◦ denotes concatenation) and then use the mapping 07→ 00,17→ 11,7→ 01 to convert this into a string of bits. To reduce notational clutter, instead of hx,yi we usehx,yi to x y denote not only the pair consisting of x and y but also the representation of this pair as a binary string. Similarly, we usehx,y,zi to denote both the ordered triple consisting of x,y,z and its representation, and use similar notation for 4-tuples, 5-tuples etc.. 1.1.2 Decision problems / languages An important special case of functions mapping strings to strings is the case of Boolean functions, whose output is a single bit. We identify such a function f with the set L =x:f(x)=1 and f callsuchsets languages or decision problems (we usethese termsinterchangeably). We identifythe computational problem of computing f (i.e., given x compute f(x)) with the problem of deciding the language L (i.e., given x, decide whether x∈L ). f f Example 1.1 By representing the possible invitees to a dinner party with the vertices of a graph having an edge between any two people that can’t stand one another, the dinner party computational problem from the introduction becomes the problem of finding a maximum sized independent set (set of vertices not containing any edges) in a given graph. The corresponding language is: INDSET=hG,ki:∃S⊆V(G) s.t.S≥k and∀u,v∈S,uv6∈E(G) An algorithm to solve this language will tell us, on input a graph G and a number k, whether there exists a conflict-free set of invitees, called an independent set, of size at least k. It is not immediately clear that such an algorithm can be used to actually find such a set, but we will see this is the case in Chapter 2. For now, let’s take it on faith that this is a good formalization of this problem. 1.1.3 Big-Oh notation Asmentionedabove,wewilltypicallymeasurethecomputationalefficiencyalgorithmasthenumber of a basic operations it performs as a function of its input length. That is, the efficiency of an algorithm can be captured by a function T from the set of natural numbersN to itself such that T(n) is equal to the maximum number of basic operations that the algorithm performs on inputs of length n. However, this function is sometimes be overly dependant on the low-level details of ourdefinitionofabasicoperation. Forexample, theadditionalgorithm willtakeaboutthreetimes more operations if it uses addition of single digit binary (i.e., base 2) numbers as a basic operation, as opposed to decimal (i.e., base 10) numbers. To help us ignore these low level details and focus on the big picture, the following well known notation is very useful: Web draft 2007-01-08 21:59 DRAFT

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.