vi 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 Lemma2.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) n 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.42NL=coNL..··.··.···…··············· .p4.13(87) Chapter notes and history............···. ·p4.14(88) Exercises ···············p4.14(88) Web draft2007-01-0821:59DRAFT vi 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