**Proceedings of Symposia in Applied Mathematics**

Volume: 38;
1989;
128 pp;
Softcover

MSC: Primary 68;

Print ISBN: 978-0-8218-0131-4

Product Code: PSAPM/38

List Price: $53.00

Individual Member Price: $42.40

**Electronic ISBN: 978-0-8218-9253-4
Product Code: PSAPM/38.E**

List Price: $53.00

Individual Member Price: $42.40

# Computational Complexity Theory

Share this page *Edited by *
*Juris Hartmanis*

Computational complexity theory is the study of the quantitative laws
that govern computing. During the last 25 years, this field has grown into a
rich mathematical theory. Currently one of the most active research areas in
computer science, complexity theory is of considerable interest to
mathematicians as well, since some of the key open problems in this field raise
basic questions about the nature of mathematics. Many experts in complexity
theory believe that, in coming decades, the strongest influence on the
development of mathematics will come from the extended use of computing and
from concepts and problems arising in computer science.

This volume contains the proceedings of the AMS Short Course on
Computational Complexity Theory, held at the Joint Mathematics Meetings in
Atlanta in January 1988. The purpose of the short course was to provide an
overview of complexity theory and to describe some of the current developments
in the field. The papers presented here represent contributions by some of the
top experts in this burgeoning area of research.

#### Table of Contents

# Table of Contents

## Computational Complexity Theory

- Table of Contents vii8 free
- Preface ix10 free
- Overview of Computational Complexity Theory 112 free
- The Isomorphism Conjecture And Sparse Sets 1829
- Restricted Relativizations of Complexity Classes 4758
- Descriptive and Computational Complexity 7586
- Complexity Issues in Cryptography 92103
- Interactive Proof Systems 108119