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
Introduction to Computational Complexityby 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.
(9640 views)
Computational Complexity: A Conceptual Perspectiveby 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.
(11840 views)
Measure-Preserving Systemsby Karl Petersen - University of North Carolina
These notes provide an introduction to the subject of measure-preserving dynamical systems, discussing the dynamical viewpoint; how and from where measure-preserving systems arise; the construction of measures and invariant measures; etc.
(10769 views)
Complexity and Computationby 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.
(15626 views)