COMPUTATIONAL COMPLEXITY (M1, Papadimitriou)

Lecture Topic : (Computer Theory) COMPUTATIONAL COMPLEXITY (M1, Papadimitriou)

Prerequisites : Theory of Computation (Sen);

Recommended Text(s) :

“Computational Complexity”, Christos H. Papadimitriou, Addison Wesley, 2004.

Approx price new on Amazon.com : $44

Approx price second hand on Amazon.com : $42

Availability free on eMule.com : Yes

eMule search key word(s) : Papadimitriou , Computational Complexity

Lectures and Links :

—–

Lecture 1  (link)

Ch.1   Problems and Algorithms

—–

Lecture 2  (link)

Ch.2   Turing Machines

—–

Lecture 3  (link)

Ch.3   Undecidability

—–

Lecture 4 (link)

Ch.4   Boolean Logic

—–

Lecture 5  (link)

Ch.5   First-Order Logic

—–

Lecture 6  (link)

Ch.6   Undecidability in Logic

—–

Lecture 7  (link)

Ch.7   Relations between Complexity Classes

—–

Lecture 8  (link)

Ch.8   Reductions and Completeness

—–

Lecture 9  (link)

Ch.9   NP-Complete Problems

—–

Lecture 10  (link)

Ch.10   coNP and Function Problems

—–

Lecture 11  (link)

Ch.11   Randomized Computation

—–

Lecture 12  (link)

Ch.12   Cryptography

—–

Lecture 13  (link)

Ch.13   Approximability

—–

Lecture 14  (link)

Ch.14   On P vs. NP

—–

Lecture 15  (link)

Ch.15   Parallel Computation

—–

Lecture 16  (link)

Ch.16   Logarithmic Space

—–

Lecture 17  (link)

Ch.17   The Polynomial Hierarchy

—–

Lecture 18  (link)

Ch.18   Computation that Counts

—–

Lecture 19  (link)

Ch.19   Polynomial Space

—–

Lecture 20  (link)

Ch.20   A Glimpse Beyond

—–