iv at many classes of readers: Physicists,mathematicians,and other scientists.This group has become increasingly inter- ested in computational complexity theory,especially because of high-profile results such as Shor's algorithm and the recent deterministic test for primality.This intellectually sophisti- cated group will be able to quickly read through Part I.Progressing on to Parts II and III they can read individual chapters and find almost everything they need to understand current research. Computer scientists (e.g.,algorithms designers)who do not work in complerity theory per se. They may use the book for self-study or even to teach a graduate course or seminar. All those-professors or students-who do research in complerity theory or plan to do so. They may already know Part I and use the book for Parts II and III,possibly in a seminar or reading course.The coverage of advanced topics there is detailed enough to allow this. This book can be used as a textbook for several types of courses.We will provide several teaching plans and material for such courses on the book's web site. Undergraduate Theory of Computation Course.Part I may be suitable for an undergraduate course that is an alternative to the more traditional Theory of Computation course currently taught in most computer science departments (and exemplified by Sipser's excellent book with the same name [SIP96]).Such a course would have a greater emphasis on modern topics such as probabilistic algorithms and cryptography.We note that in contrast to Sipser's book, the current book has a quite minimal coverage of computability and no coverage of automata theory,but we provide web-only chapters with more coverage of these topics on the book's web site.The prerequisite mathematical background would be some comfort with mathematical proofs and elementary probability on finite sample spaces,topics that are covered in typical “discrete math”/“math for CS”courses currently offered in most CS departments. Advanced undergraduate/beginning graduate introduction to complerity course.The book can be used as a text for an introductory complexity course aimed at undergraduate or non-theory graduate students (replacing Papadimitriou's 1994 book [Pap94]that does not contain many recent results).Such a course would probably include many topics from Part I and then a sprinkling from Parts II and III,and assume some background in algorithms and/or the theory of computation. Graduate Complerity course.The book can serve as a text for a graduate complexity course that prepares graduate students interested in theory to do research in complexity and related areas.Such a course can use parts of Part I to review basic material,and then move on to the advanced topics of Parts II and III.The book contains far more material than can be taught in one term,and we provide on our website several alternative outlines for such a course We hope that this book conveys our excitement about this new field and the insights it provides in a host of older disciplines. DRAFT Web draft2007-01-0821:59DRAFT iv at many classes of readers: • Physicists, mathematicians, and other scientists. This group has become increasingly inter￾ested in computational complexity theory, especially because of high-profile results such as Shor’s algorithm and the recent deterministic test for primality. This intellectually sophisti￾cated group will be able to quickly read through Part I. Progressing on to Parts II and III they can read individual chapters and find almost everything they need to understand current research. • Computer scientists (e.g., algorithms designers) who do not work in complexity theory per se. They may use the book for self-study or even to teach a graduate course or seminar. • All those —professors or students— who do research in complexity theory or plan to do so. They may already know Part I and use the book for Parts II and III, possibly in a seminar or reading course. The coverage of advanced topics there is detailed enough to allow this. This book can be used as a textbook for several types of courses. We will provide several teaching plans and material for such courses on the book’s web site. • Undergraduate Theory of Computation Course. Part I may be suitable for an undergraduate course that is an alternative to the more traditional Theory of Computation course currently taught in most computer science departments (and exemplified by Sipser’s excellent book with the same name [SIP96]). Such a course would have a greater emphasis on modern topics such as probabilistic algorithms and cryptography. We note that in contrast to Sipser’s book, the current book has a quite minimal coverage of computability and no coverage of automata theory, but we provide web-only chapters with more coverage of these topics on the book’s web site. The prerequisite mathematical background would be some comfort with mathematical proofs and elementary probability on finite sample spaces, topics that are covered in typical “discrete math”/“math for CS” courses currently offered in most CS departments. • Advanced undergraduate/beginning graduate introduction to complexity course. The book can be used as a text for an introductory complexity course aimed at undergraduate or non-theory graduate students (replacing Papadimitriou’s 1994 book [Pap94] that does not contain many recent results). Such a course would probably include many topics from Part I and then a sprinkling from Parts II and III, and assume some background in algorithms and/or the theory of computation. • Graduate Complexity course. The book can serve as a text for a graduate complexity course that prepares graduate students interested in theory to do research in complexity and related areas. Such a course can use parts of Part I to review basic material, and then move on to the advanced topics of Parts II and III. The book contains far more material than can be taught in one term, and we provide on our website several alternative outlines for such a course. We hope that this book conveys our excitement about this new field and the insights it provides in a host of older disciplines. Web draft 2007-01-08 21:59