Contents About this book 进 Introduction p0.1(1) I Basic Complexity Classes p0.9(9) 1 The computational model-and why it doesn't matter p1.1(11) l.1 Encodings and Languages:Some conventions.··.·...·..··.. p1.2(12) l.l.1 Representing objects as strings·················· ··。 ·p1.2(12) 1.1.2 Decision problems languages p1.3(13) 1.1.3Big-Oh notation...··..·. p1.3(13) 1.2 Modeling computation and efficiency .p1.4(14) l.2.1 The Turing Machine........·.···. p1.5(15) 1.2.2 Robustness of our definition...··.···. .p1.9(19) 1.2.3 The expressive power of Turing machines..... p1.12(22) 1.3 Machines as strings and the universal Turing machines. p1.12(22) l.3.1 The Universal Turing Machine..·····.···. p1.13(23) 1.4 Uncomputable functions..........·.······. p1.15(25) 1.4.1 The Halting Problem......... .p1.15(25) 1.5 Deterministic time and the class P....... .p1.17(27) 1.5.1 On the philosophical importance of P .p1.17(27) 1.5.2 Criticisms of P and some efforts to address them . .p1.18(28) 1.5.3 Edmonds'quote·························· .p1.19(29) Chapter notes and history....,·.....,..·。...·..·····.·· .p1.20(30) Exercises·········· ·p1.21(31) 1.A Proof of Theorem 1.13:Universal Simulation in O(Tlog T)-time .......... p1.25(35) 2 NP and NP completeness p2.1(39) 2.1 The class NP..···.· ····p2.2(40) 2.1.1 Relation between NP and P ....p2.3(41) 2.1.2Non-deterministic Turing machines...··.··.···.··.· ··...p2.4(42) 2.2 Reducibility and NP-completeness··,·························p2.5(43) Web draft2007-01-0821:59 Complexity Theory:A Modern Approach.C2006 Sanjeev Arora and Boaz Barak.References and attributions are still incomplete.DRAFT Contents About this book iii Introduction p0.1 (1) I Basic Complexity Classes p0.9 (9) 1 The computational model —and why it doesn’t matter p1.1 (11) 1.1 Encodings and Languages: Some conventions . . . . . . . . . . . . . . . . . . . . . . p1.2 (12) 1.1.1 Representing objects as strings . . . . . . . . . . . . . . . . . . . . . . . . . . p1.2 (12) 1.1.2 Decision problems / languages . . . . . . . . . . . . . . . . . . . . . . . . . . p1.3 (13) 1.1.3 Big-Oh notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p1.3 (13) 1.2 Modeling computation and efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . p1.4 (14) 1.2.1 The Turing Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p1.5 (15) 1.2.2 Robustness of our definition. . . . . . . . . . . . . . . . . . . . . . . . . . . . p1.9 (19) 1.2.3 The expressive power of Turing machines. . . . . . . . . . . . . . . . . . . . . p1.12 (22) 1.3 Machines as strings and the universal Turing machines. . . . . . . . . . . . . . . . . p1.12 (22) 1.3.1 The Universal Turing Machine . . . . . . . . . . . . . . . . . . . . . . . . . . p1.13 (23) 1.4 Uncomputable functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p1.15 (25) 1.4.1 The Halting Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p1.15 (25) 1.5 Deterministic time and the class P. . . . . . . . . . . . . . . . . . . . . . . . . . . . . p1.17 (27) 1.5.1 On the philosophical importance of P . . . . . . . . . . . . . . . . . . . . . . p1.17 (27) 1.5.2 Criticisms of P and some efforts to address them . . . . . . . . . . . . . . . . p1.18 (28) 1.5.3 Edmonds’ quote . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p1.19 (29) Chapter notes and history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p1.20 (30) Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p1.21 (31) 1.A Proof of Theorem 1.13: Universal Simulation in O(T log T)-time . . . . . . . . . . . p1.25 (35) 2 NP and NP completeness p2.1 (39) 2.1 The class NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p2.2 (40) 2.1.1 Relation between NP and P . . . . . . . . . . . . . . . . . . . . . . . . . . . p2.3 (41) 2.1.2 Non-deterministic Turing machines. . . . . . . . . . . . . . . . . . . . . . . . p2.4 (42) 2.2 Reducibility and NP-completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . p2.5 (43) Web draft 2007-01-08 21:59 Complexity Theory: A Modern Approach. © 2006 Sanjeev Arora and Boaz Barak. References and attributions are still incomplete. v