Complexity of Algorithms

Complexity of Algorithms

These notes deal with the foundations of measuring the complexity of a problem, algorithm or structure used in computer science, the traditional branches of mathematics, statistical physics, biology, medicine, social sciences and engineering.

Publication date: 31 Dec 1999

ISBN-10: n/a

ISBN-13: n/a

Paperback: 242 pages

Views: 25,761

Type: N/A

Publisher: n/a

License: n/a

Post time: 09 Dec 2006 07:38:21

Complexity of Algorithms

Complexity of Algorithms These notes deal with the foundations of measuring the complexity of a problem, algorithm or structure used in computer science, the traditional branches of mathematics, statistical physics, biology, medicine, social sciences and engineering.
Tag(s): Theory of Computation
Publication date: 31 Dec 1999
ISBN-10: n/a
ISBN-13: n/a
Paperback: 242 pages
Views: 25,761
Document Type: N/A
Publisher: n/a
License: n/a
Post time: 09 Dec 2006 07:38:21
Document Excerpts:

The need to be able to measure the complexity of a problem, algorithm or structure, and to obtain bounds and quantitive relations for complexity arises in more and more sciences: besides computer science, the traditional branches of mathematics, statistical physics, biology, medicine, social sciences and engineering are also confronted more and more frequently with this problem. In the approach taken by computer science, complexity is measured by the quantity of computational resources (time, storage, program, communication) used up by a particular task. These notes deal with the foundations of this theory.

Computation theory can basically he divided into three parts of different character. First, the exact notions of algorithm, time, storage capacity, etc. must be introduced. For this, different mathematical machine models must be defined, and the time and storage needs of the computations performed on these need to be clarified (this is generally measured as a function of the size of input). By limiting the available resources, the range of solvable problems gets narrower; this is how we arrive at different complexity classes.

Second, one must determine the resource need of the most important algorithms in various areas of mathematics, and give efficient algorithms to prove that certain important problems belong to certain complexity classes. In these notes, we do not strive for completeness in the investigation of concrete algorithms and problems; this is the task of the corresponding fields of mathematics (combinatorics, operations research, numerical analysis, number theory). Nevertheless, a large number of concrete algorithms will be described and analyzed to illustrate certain notions and methods, and to establish the complexity of certain problems.

Third, one must find methods to prove "negative results", i.e. for the proof that some problems are actually unsolvable under certain resource restrictions. Often, these questions can be formulated by asking whether certain complexity classes are different or empty. This problem area includes the question whether a problem is algorithmically solvable at all; this question can today be considered classical, and there are many important results concerning it; in particular, the decidability or undecidablity of most concrete problems of interest is known.

It is, finally, worth noting that if a problem turns out to be "difficult" to solve, this is not necessarily a negative result. More and more areas (random number generation, communication protocols, cryptography, data protection) need problems and structures that are guaranteed to be complex. These are important areas for the application of complexity theory, from among them, we will deal with random number generation and cryptography, the theory of secret communication.
 




About The Author(s)


Péter Gács is a Professor in the Computer Science Department of the Boston University. His research interests are fault-tolerant cellular automata, algorithmic information theory, computational complexity theory, and quantum information theory.

Péter Gács

Péter Gács is a Professor in the Computer Science Department of the Boston University. His research interests are fault-tolerant cellular automata, algorithmic information theory, computational complexity theory, and quantum information theory.


László Lovász is a Professor in the Department of Computer Science of the Eötvös Loránd University in Budapest, Hungary. His research topics cover combinatorial optimization, algorithms, complexity, graph theory, and random walks.

László Lovász

László Lovász is a Professor in the Department of Computer Science of the Eötvös Loránd University in Budapest, Hungary. His research topics cover combinatorial optimization, algorithms, complexity, graph theory, and random walks.


Book Categories
Sponsors