10.4 Additional NP-Complete Problems.................447

10.4Л Describing NP-complete Problems.............447

10.4.2 The Problem of Independent Sets..............448

10.4.3 The Node-Cover Problem..................452

10.4.4 The Directed Hamilton-Circuit Problem..........453

10.4.5 Undirected Hamilton Circuits and the TSP........460

10.4.6 Summary of NP-Complete Problems............461

10.4.7 Exercises for Section 10.4..................462

10.5 Summary of Chapter 10.......................466

10.6 References for Chapter 10......................467

11 Additional Classes of Problems 469

11.1 Complements of Languages in AfT.................470

11.1.1 The Class of Languages Co-AfV ..............470

11.1.2 NP-Complete Problems and Co-NV............471

11.1.3 Exercises for Section 11,1..................472

11.2 Problems Solvable in Polynomial Space ..............473

11.2.1 Polynomial-Space Turing Madiinea.............473

11.2.2 Relationship oiVS and MVS to Previously Defined ClasBes474

11.2.3 Deterministic and Nondeterministic Polynomial Space . . 476

11.3 A Problem That Is Complete for 5................478

11.3.1 PS-Completeness.......................478

11.3.2 Quantified Boolean Formulas................479

11.3.3 Evaluating Quantified Boolean Formulas..........480

11.3.4 PS-Completeness of the QBF Problem...........482

11.3.5 Exercises for Section 11.3..................487

11.4 Language Classes Based on Randomization............487

11.4.1 Quicksort: an Example of a Randomized Algorithm , , .488

11.4.2 A Turing-Machine Model Using Randomization......489

11.4.3 The Language of a Randomized Turing Machine.....490

11.4.4 The Class ТгГ ........................492

11.4.5 Recognizing Languages in ItV ...............494

11.4.6 The Class ZW .......................495

11.4.7 Relationship Between :R.:P and ............496

11.4.8 Relationships to the Classes P and ЛТ..........497

11.5 The Complexity of Primality Testing................498

11.5.1 The Importance of Testing Primality............499

11.5.2 Introduction to Modular Arithmetic............501

11.5.3 The Complexity of Modular-Arithmetic Computations . . 503

11.5.4 Random-Polynomial Primality Testing...........504

11.5.5 Nondeterministic Primality Tests..............505

11.5.6 Exercises for Section 11.5..................508

11.6 Summary of Chapter 11.......................508

11.7 References for Chapter 11......................510

Index 513