Introduction to Complexity Theory
by Oded Goldreich
1999
Number of pages: 375
Description:
Complexity Theory is a central field of Theoretical Computer Science, with a remarkable list of celebrated achievements as well as a very vibrant present research activity. The field is concerned with the study of the intrinsic complexity of computational tasks, and this study tend to aim at generality: It focuses on natural computational resources, and the effect of limiting those on the class of problems that can be solved. These lecture notes were taken by students attending my year-long introductory course on Complexity Theory, given in 1998-99 at the Weizmann Institute of Science. The course was aimed at exposing the students to the basic results and research directions in the field. The focus was on concepts and ideas, and complex technical proofs were avoided. It was assumed that students have taken a course in computability, and hence are familiar with Turing Machines.
Download or read it online for free here:
Download link
(2.3MB, PDF)
Similar books
Complexity Theory: A Modern Approachby Sanjeev Arora, Boaz Barak - Cambridge University Press
The book provides an introduction to basic complexity classes, lower bounds on resources required to solve tasks on concrete models such as decision trees or circuits, derandomization and pseudorandomness, proof complexity, quantum computing, etc.
(17570 views)
Algorithms and Complexityby Herbert S. Wilf - AK Peters, Ltd.
An introductory textbook on the design and analysis of algorithms. Recursive algorithms are illustrated by Quicksort, FFT, and fast matrix multiplications. Algorithms in number theory are discussed with some applications to public key encryption.
(21110 views)
Measure-Preserving Systemsby Karl Petersen - University of North Carolina
These notes provide an introduction to the subject of measure-preserving dynamical systems, discussing the dynamical viewpoint; how and from where measure-preserving systems arise; the construction of measures and invariant measures; etc.
(10766 views)
Mathematics and Computationby Avi Wigderson - Princeton University Press
The book provides a broad, conceptual overview of computational complexity theory -- the mathematical study of efficient computation. It is useful for undergraduate and graduate students in mathematics, computer science, and related fields.
(3335 views)