Lovász László

Complexity of algorithms

The study of the complexity of algorithms started in the 1930’s,

principally with the development of the concepts of Turing machine and algorithmic

decidability. Through the spread of computers and the increase of

their power this discipline achieved higher and higher significance.

In these lecture notes we discuss the classical foundations of complexity theory

like Turing machines and the halting problem, as well as some leading

new developments: information and communication complexity, generation

of pseudorandom numbers, parallel algorithms, foundations of cryptography

and interactive proofs.


Ajánlott könyvek