Introduction to Complexity Theory

The notes are aimed at exposing the students to the basic results and research directions in the field of Complexity Theory. The focus was on concepts and ideas, and complex technical proofs were avoided.

**Tag(s):**
Theory of Computation

**Publication date**: 31 Dec 1999

**ISBN-10**:
n/a

**ISBN-13**:
n/a

**Paperback**:
n/a

**Views**: 17,302

**Type**: N/A

**Publisher**:
n/a

**License**:
n/a

**Post time**: 02 Apr 2007 06:58:37

Introduction to Complexity Theory

The notes are aimed at exposing the students to the basic results and research directions in the field of Complexity Theory. The focus was on concepts and ideas, and complex technical proofs were avoided.

Terms and Conditions:

From the Preface:

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. Specific topics included:

- Revisiting NP and NPC (with emphasis on search vs decision);

- Complexity classes defined by one resource-bound - hierarchies, gaps, etc;

- Non-deterministic Space complexity (with emphasis on NL);

- Randomized Computations (e.g., ZPP, RP and BPP);

- Non-uniform complexity (e.g., P/poly, and lower bounds on restricted circuit classes);

- The Polynomial-time Hierarchy;

- The counting class #P, approximate-#P and uniqueSAT;

- Probabilistic proof systems (i.e., IP, PCP and ZK);

- Pseudorandomness (generators and derandomization);

- Time versus Space (in Turing Machines);

- Circuit-depth versus TM-space (e.g., AC, NC, SC);

- Average-case complexity;

It was assumed that students have taken a course in computability, and hence are familiar with Turing Machines.

Most of the presented material is quite independent of the specific (reasonable) model of computation, but some (e.g., Lectures 5, 16, and 19-20) depends heavily on the locality of computation of Turing machines.

Oded Goldreich wrote:Copyright (C symbol) 1999 by Oded Goldreich. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Abstracting with credit is permitted.

From the Preface:

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. Specific topics included:

- Revisiting NP and NPC (with emphasis on search vs decision);

- Complexity classes defined by one resource-bound - hierarchies, gaps, etc;

- Non-deterministic Space complexity (with emphasis on NL);

- Randomized Computations (e.g., ZPP, RP and BPP);

- Non-uniform complexity (e.g., P/poly, and lower bounds on restricted circuit classes);

- The Polynomial-time Hierarchy;

- The counting class #P, approximate-#P and uniqueSAT;

- Probabilistic proof systems (i.e., IP, PCP and ZK);

- Pseudorandomness (generators and derandomization);

- Time versus Space (in Turing Machines);

- Circuit-depth versus TM-space (e.g., AC, NC, SC);

- Average-case complexity;

It was assumed that students have taken a course in computability, and hence are familiar with Turing Machines.

Most of the presented material is quite independent of the specific (reasonable) model of computation, but some (e.g., Lectures 5, 16, and 19-20) depends heavily on the locality of computation of Turing machines.

Tweet

About The Author(s)

No information is available for this author.

Book Categories

Computer Science
Introduction to Computer Science
Introduction to Computer Programming
Algorithms and Data Structures
Artificial Intelligence
Computer Vision
Machine Learning
Neural Networks
Game Development and Multimedia
Data Communication and Networks
Coding Theory
Computer Security
Information Security
Cryptography
Information Theory
Computer Organization and Architecture
Operating Systems
Image Processing
Parallel Computing
Concurrent Programming
Relational Database
Document-oriented Database
Data Mining
Big Data
Data Science
Digital Libraries
Compiler Design and Construction
Functional Programming
Logic Programming
Object Oriented Programming
Formal Methods
Software Engineering
Agile Software Development
Information Systems
Geographic Information System (GIS)

Mathematics
Mathematics
Algebra
Abstract Algebra
Linear Algebra
Number Theory
Numerical Methods
Precalculus
Calculus
Differential Equations
Category Theory
Proofs
Discrete Mathematics
Theory of Computation
Graph Theory
Real Analysis
Complex Analysis
Probability
Statistics
Game Theory
Queueing Theory
Operations Research
Computer Aided Mathematics

Supporting Fields
Web Design and Development
Mobile App Design and Development
System Administration
Cloud Computing
Electric Circuits
Embedded System
Signal Processing
Integration and Automation
Network Science
Project Management

Operating System
Programming/Scripting
Ada
Assembly
C / C++
Common Lisp
Forth
Java
JavaScript
Lua
Microsoft .NET
Rexx
Perl
PHP
Python
R
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors