The strive for efficiency is ancient and universal, as time and other resources are always in shortage. Thus, the question of which tasks can be performed efficiently is central to the human experience. A key step towards the systematic study of the aforementioned question is a rigorous definition of the notion of a task and of procedures for solving tasks. These definitions were provided by computability theory, which emerged in the 1930's. This theory focuses on computational tasks, and considers automated procedures (i.e., computing devices and algorithms) that may solve such tasks.

The strive for efficiency is ancient and universal,
as time and other resources are always in shortage.
Thus, the question of which tasks can be performed efficiently
is central to the human experience.

Computational complexity theory has developed rapidly in the past three decades.

The present set of notes have grown out of a set of courses I have given at
the Royal Institute of Technology. The courses have been given at an in-
troductory graduate level, but also interested undergraduates have followed
the courses.

The main idea of the course has been to give the broad picture of mod-
ern complexity theory. To dene the basic complexity classes, give some
examples of each complexity class and to prove the most standard relations.
The set of notes does not contain the amount of detail wanted from a text-

For the past several years mathematics majors in the computing track at the University of Pennsylvania have taken a course in continuous algorithms (numerical analysis) in the junior year, and in discrete algorithms
in the senior year. This book has grown out of the senior course as I have been teaching it recently. It has also been tried out on a large class of computer science and mathematics majors, including seniors and graduate students, with good results.