Computational Complexity Theory
0368-3168-01
[Thursday 9am- 12pm]
[Syllabus]
[Messages]
[Exercises]
Presentations:
Introduction
Preliminaries; Reductions
Cook Theorem
NP-complete Problems;
Paths; 2SAT
Space Complexity
Approximation Algorithms; TSP;
Hardness of Approximation
Cryptography
The Polynomial-time Hierarchy and BPP
coNP and Primality
Random Walks
Zero Knowledge Proofs