Computational complexity is the study of the inherent diculty of computational 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.