NEWS FLASH:
Eight hundred and fifty transparencies that can be used in your course
are now available for download
from the book's
transparencies page
Publisher's Blurb
List of Chapters
Preface, Table of Contents, Sample Chapters, and the Index
Transparency Masters That Can Be Used to Teach The Book
Order From Amazon
Publisher's Catalog Entry
How to Get A Desk Copy From The Publisher
Errata
The Complexity Theory Companion is an accessible, algorithmically
oriented, research-centered, up-to-date guide to some of the most
interesting techniques of complexity theory.
The book's thesis is that simple algorithms are at the heart of
complexity theory. From the tree-pruning and interval-pruning
algorithms that shape the first chapter to the query simulation
procedures that dominate the last chapter, the central proof methods
of the book are algorithmic. And to more clearly highlight the role
of algorithmic techniques in complexity theory, the book is---unlike
other texts on complexity---organized by technique rather than by
topic. Each chapter of this book focuses on one technique: what it
is, and what results and applications it yields.
This textbook was developed at the University of Rochester in courses
given to graduate students and advanced undergraduates. Researchers
also will find this book a valuable source of reference due to the
comprehensive bibliography of close to five hundred entries, the
thirty-five page subject index, and the appendices giving overviews of
complexity classes and reductions.
Preface. The Self-Reducibility Technique. The One-Way Function
Technique. The Tournament Divide and Conquer Technique. The
Isolation Technique. The Witness Reduction Technique. The Polynomial
Interpolation Technique. The Nonsolvable Group Technique. The Random
Restriction Technique. The Polynomial Technique. A Rogues' Gallery
of Complexity Classes. A Rogues' Gallery of Reductions. References.
Index.
-
The Preface:
(as pdf),
(as postscript).
-
The Table of Contents:
(as pdf),
(as postscript).
-
The Self-Reducibility Technique:
(as pdf),
(as postscript).
(This chapter covers
whether NP is likely to have sparse complete sets, and whether
any sparse sets at all are likely to be in NP-P. Coverage
includes the Left Set Technique, the
Hartmanis-Immerman-Sewelson Encoding, Mahaney's Theorem,
and the Ogiwara-Watanabe Theorem.)
-
The Isolation Technique:
(as pdf),
(as postscript).
(This chapter's coverage
includes the Isolation Lemma, the Valiant-Vazirani Theorem, Toda's Theorem,
and the Wigderson/Gal/Allender/Reinhardt
work that led to NL/poly=UL/poly.)
-
The Index:
(as pdf),
(as postscript).
Six hundred nifty,
student-made transparencies that can be used to teach
seven of the nine chapters of the book are available for download
from the book's
Transparencies Page
If you are in North America
and are seriously interested
in possibly using the book as a course text,
you can request
a desk copy from
Springer (New York).
If you are outside of North America
and are seriously interested
in possibly using the book as a course text,
you can request
a desk copy from
Springer (Germany).
Return to Top of Page
