**Complexity Theory**

by Johan Håstad

2008**Number of pages**: 130

**Description**:

The main idea of the course has been to give the broad picture of modern complexity theory. To define the basic complexity classes, give some examples of each complexity class and to prove the most standard relations. The set of notes does not contain the amount of detail wanted from a text book. I have taken the liberty of skipping many boring details and tried to emphasize the ideas involved in the proofs. Probably in many places more details would be helpful and I would he grateful for hints on where this is the case. Most of the notes are at a fairly introductory level but some of the section contain more advanced material. This is in particular true for the section on pseudorandom number generators and the proof that IP = PSPACE. Anyone getting stuck in these parts of the notes should not be disappointed.

Download or read it online for free here:

**Download link**

(0.7MB, PDF)

## Similar books

**Computability and Complexity from a Programming Perspective**

by

**Neil D. Jones**-

**The MIT Press**

The author builds a bridge between computability and complexity theory and other areas of computer science. Jones uses concepts familiar from programming languages to make computability and complexity more accessible to computer scientists.

(

**11171**views)

**Introduction to Complexity Theory**

by

**Oded Goldreich**

Complexity theory is the study of the intrinsic complexity of computational tasks. The book is aimed at exposing the students to the basic results and research directions in the field. The focus was on concepts, complex technical proofs were avoided.

(

**10206**views)

**Complexity and Computation**

by

**Allen Downey**-

**Green Tea Press**

This book is about data structures and algorithms, intermediate programming in Python, complexity science and the philosophy of science. The book covers Graphs, Analysis of algorithms, Scale-free networks, Cellular Automata, Agent-based models, etc.

(

**15003**views)

**Parallel Complexity Theory**

by

**Ian Parberry**-

**Prentice Hall**

The rapid growth of parallel complexity theory has led to a proliferation of parallel machine models. This book presents a unified theory of parallel computation based on a network model. It is the first such synthesis in book form.

(

**8919**views)