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.

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 field 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 resources required to solve
a computational task (or a class of such tasks),
rather than at a specific algorithm or an algorithmic schema.
Actually, research in Complexity Theory tends to
start with and focus on the computational resources themselves,
and addresses the effect of limiting these resources on the class
of tasks that can be solved.
Thus, Computational Complexity is the study of the
what can be achieved within limited time
(and/or other limited natural computational resources).

To Download this E-Book Click Here.