Logo

Introduction to Complexity Theory

Introduction to Complexity Theory
by


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.

Home page url

Download or read it online for free here:
Download link
(2.3MB, PDF)

Similar books

Book cover: Lecture Notes on Computational ComplexityLecture Notes on Computational Complexity
by
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.
(14904 views)
Book cover: Complexity TheoryComplexity Theory
by
This set of notes gives the broad picture of modern complexity theory, defines the basic complexity classes, gives some examples of each complexity class and proves the most standard relations. The author emphasizes the ideas involved in the proofs.
(16146 views)
Book cover: Mathematics and ComputationMathematics and Computation
by - Princeton University Press
The book provides a broad, conceptual overview of computational complexity theory -- the mathematical study of efficient computation. It is useful for undergraduate and graduate students in mathematics, computer science, and related fields.
(3081 views)
Book cover: Computational Complexity: A Conceptual PerspectiveComputational Complexity: A Conceptual Perspective
by - 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.
(11591 views)