Computational Complexity
A Conceptual Perspective
Oded Goldreich
Department of Computer Science and Applied Mathematics
Weizmann Institute of Science Rehovot Israel
December
I
to Dana
c□Copyright by Oded Goldreich
Permission to make copies of part or all of this work for personal or classroom use is
granted without fee provided that copies are not made or distributed for prot or com
mercial advantage and that new copies bear this notice and the full citation on the rst
page Abstracting with credit is permitted
II
Preface
The strive for eciency is ancient and universal as time and other resources are
always in shortage Thus the question of which tasks can be performed eciently
is central to the human experience
A key step towards the systematic study of the aforementioned question is a
rigorous denition of the notion of a task and of procedures for solving tasks These
denitions were provided by computability theory which emerged in the
s
This theory focuses on computational tasks and considers automated procedures
ie computing devices and algorithms that may solve such tasks
In focusing attention on computational tasks and algorithms computability
theory has set the stage for the study of the computational resources like time that
are required by such algorithms When this study focuses on the resources that are
necessary for any algorithm that solves a particular task or a task of a particular
type the study becomes part of the theory of Computational Complexity also
known as Complexity Theory □
Complexity Theory is a central eld of the theoretical foundations of Computer
Science It is concerned with the study of the intrinsic complexity of computational
tasks That is a typical Complexity theoretic study looks at the computational re
sources required to solve a computational task or a class of such tasks rather than
at a specic algorithm or an algorithmic schema Actually research in Complexity
Theory tends to start with and focus on the computation