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

**P, NP, and NP-Completeness: The Basics of Complexity Theory**

by

**Oded Goldreich**-

**Cambridge University Press**

The main focus of the current book is on the P-vs-NP Question and the theory of NP-completeness. Additional topics that are covered include the treatment of the general notion of a reduction between computational problems.

(

**5089**views)

**Computational Complexity: A Conceptual Perspective**

by

**Oded Goldreich**-

**Cambridge University Press**

This book offers a comprehensive perspective to modern topics in complexity theory. It can be used as an introduction as either a textbook or for self-study, or to experts, since it provides expositions of the various sub-areas of complexity theory.

(

**7208**views)

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

(

**9681**views)

**Algorithms and Complexity**

by

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

(

**13548**views)