The discipline of Computer Science is a blend of mathematical theory and engineering oriented concepts. At the core of the science of computing is complexity theory, one of the (relatively) more established areas in a very young field. Briefly stated, the goal of complexity theory is to provide an "intrinsic" (i.e. as machine independent as possible) framework for studying the complexity of problems and the relation between various models and measures of complexity. In one sense, the theory has been very successful in the identification of natural and invariant complexity classes and in identifying the fundamental issues. On the other hand, we have been largely unsuccessful to date in efforts to prove that particular computational problems are difficult to solve. But the field continues to progress and one sign of this progress is the number of related topics that have emerged. For example, modern cryptography is strongly based on complexity theoretic assumptions and concepts, and interactive proofs have led to new insights into approximation algorithms.