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
Introduction to Complexity Theoryby 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.
(5647 views)
Around Kolmogorov Complexity: Basic Notions and Resultsby Alexander Shen - arXiv.org
Algorithmic information theory studies description complexity and randomness. This text covers the basic notions of algorithmic information theory: Kolmogorov complexity, Solomonoff universal a priori probability, effective Hausdorff dimension, etc.
(888 views)
Algorithmic Randomness and Complexityby R. G. Downey, D. R. Hirschfeldt - Springer
Computability and complexity theory are two central areas of research in theoretical computer science. This book provides a systematic, technical development of algorithmic randomness and complexity for scientists from diverse fields.
(4728 views)
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.
(11526 views)