**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

**Specifying Systems**

by

**Leslie Lamport**-

**Addison-Wesley Professional**

This book shows how to write unambiguous specifications of complex computer systems. It provides a complete reference manual for the TLA+, the language developed by the author for writing simple and elegant specifications of algorithms and protocols.

(

**11760**views)

**Introduction to Computational Complexity**

by

**Martin Tompa**

Lecture notes for a graduate course on computational complexity taught at the University of Washington. Alternating Turing machines are introduced very early, and deterministic and nondeterministic Turing machines treated as special cases.

(

**7235**views)

**Lecture Notes on Computational Complexity**

by

**Luca Trevisan**

Notes from a graduate courses on Computational Complexity. The first 15 lectures cover fundamentals, the remaining is advanced material: Hastad's optimal inapproximability results, lower bounds for parity in bounded depth-circuits, and more.

(

**12226**views)

**Communication Complexity (for Algorithm Designers)**

by

**Tim Roughgarden**-

**Stanford University**

The two biggest goals of the course are: 1. Learn several canonical problems that have proved the most useful for proving lower bounds; 2. Learn how to reduce lower bounds for fundamental algorithmic problems to communication complexity lower bounds.

(

**3075**views)