Complexity theory is a flourishing area of research that continues to provide one of the richest sources of research problems in computer science. This volume, a collection of articles written by experts, provides a survey of the subjects, a comprehensive guide to research, and a provocative look to the future.

The editors' aim has been to provide an accessible description of the current state of complexity theory and to demonstrate the breadth of techniques and results that make the subject exciting. Papers are on traditional topics ranging from sublogarithmic space to exponential time, on new combinatorial techniques and recent successes such as interactive proof systems, and on the newly emerging areas of quantum and biological computing.

As a result, researchers and students in computer science will find this book an excellent starting point for study of the subject and a useful source of the key known results.