Computational Complexity Theory

 

These are presentations for an undergraduate Computational Complexity Theory course.

The same could be found at http://computational.complexity.googlepages.com/home

 

They are in a powerpoint 2007 format --- if you don't have it installed, you can find a viewer by Microsoft here.

You can find handouts versions as wellas slides in PDF format.

They are based on previous versions, which you can find here.

 

Presentations:

Introduction (pdf: handouts, slides)

Turing Machines; (pdf: handouts, slides)

NP-completeness; (pdf: handouts, slides)

2SAT;(pdf: handouts, slides)

Space Complexity (pdf: handouts, slides) pdf NL closed under complement

Approximation Problem; (pdf: handouts, slides)

PCP; (pdf: handouts) Notes for the PCP and Hardness of Approximation

PH and BPP; (pdf: handouts)

Random Walks (pdf file)

 

_______________________________________________________