CONTENTS vii 5 The Polynomial Hierarchy and Alternations p5.1(91) 5.1 The classes >2 and........·..·· ....p5.1(91) 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.2P-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 C 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) Wab.draft2007-01-0821:59DRAFT CONTENTS vii 5 The Polynomial Hierarchy and Alternations p5.1 (91) 5.1 The classes Σ p 2 and Π p 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p5.1 (91) 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