This book contains a revised version of the dissertation the author wrote at the Department of
Computer Science of the University of Chicago. The thesis was submitted to the Faculty of
Physical Sciences in conformity with the requirements for the PhD degree in June 1999. It was
honored with the 1999 ACM Doctoral Dissertation Award in May 2000. Summary Computational
complexity is the study of the inherent di culty of compu- tional problems and the power of the
tools we may use to solve them. It aims to describe how many resources we need to compute the
solution as a function of the problem size. Typical resources include time on sequential and
parallel architectures and memory space. As we want to abstract away from details of input
representation and speci cs of the computer model we end up with classes of problems that we
can solve within certain robust resource bounds such as polynomial time parallel logarithmic
time and logarithmic space. Research in complexity theory boils down to determining the
relationships between these classes { inclusions and separations. In this dissertation we
focus on the role of randomness and look at various properties of hard problems in order to
obtain separations. We also investigate the power of nondeterminism and alternation as well as
space versus time issues. Randomness provides a resource that seems to help in various
situations.
