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

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

(

**15249**views)

**From Complexity to Creativity**

by

**Ben Goertzel**-

**Plenum Press**

This text applies the concepts of complexity science to provide an explanation of all aspects of human creativity. The book describes the model that integrates ideas from computer science, mathematics, neurobiology, philosophy, and psychology.

(

**15706**views)

**Think Complexity: Complexity Science and Computational Modeling**

by

**Allen B. Downey**-

**Green Tea Press**

This book is about complexity science, data structures and algorithms, intermediate programming in Python, and the philosophy of science. The book focuses on discrete models, which include graphs, cellular automata, and agent-based models.

(

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

(

**21356**views)