Bovet D.P., Crescenzi P. Introduction to the Theory of Complexity

Издательство Prentice Hall, 2006, -291 pp.The birth of the theory of computational complexity can be set in the early 1960s when the first users of electronic computers started to pay increasing attention to the performances of their programs. As in the theory of computation, where the concept of a model of computation had led to that of an algorithm and of an algorithmically solvable problem, similarly, in the theory of computational complexity, the concept of resource used by a computation led to that of an efficient algorithm and of a computationally feasible problem.
Since these preliminary stages, many more results have been obtained and, as stated by Hartmanis (1989), ‘the systematic study of computational complexity theory has developed into one of the central and most active research areas of computer science. It has grown into a rich and exciting mathematical theory whose development is motivated and guided by computer science needs and technological advances.’
The aim of this introductory book is to review in a systematic way the most significant results obtained in this new research area. The main goals of computational complexity theory are to introduce classes of problems which have similar complexity with respect to a specific computation model and complexity measure, and to study the intrinsic properties of such classes.
In this book, we will follow a balanced approach which is partly algorithmic and partly structuralist. From an algorithmic point of view, we will first present some ‘natural’ problems and then illustrate algorithms which solve them. Since the aim is merely to prove that the problem belongs to a specific class, we will not always give the most efficient algorithm and we will occasionally give preference to an algorithm which is simpler to describe and analyse.
From a structural point of view, we will be concerned with intrinsic properties of complexity classes, including relationships between classes, implications between several hypotheses about complexity classes, and identification of structural properties of sets that affect their computational complexity.
The reader is assumed to have some basic knowledge of theory of computation (as taught in an undergraduate course on Automata Theory, Logic, Formal Languages Theory, or Theory of Computation) and of programming languages and techniques. Some mathematical knowledge is also required.
The first eight chapters of the book can be taught on a senior undergraduate course. The whole book together with an exhaustive discussion of the problems should be suitable for a postgraduate course.Mathematical preliminaries
Elements of computability
Complexity classes
The class P
The class NP
The complexity of optimization problems
Beyond NP
Space-complexity classes
Probabilistic algorithms and complexity classes
Interactive proof systems
Models of parallel computers
Parallel algorithms