Complexity Theory - information for students
Actual information, homework assignements and Q&A forum is available at
e-learning VUT
Lectures
1: Introduction
2: RAM machines
3a: Hierarchy Theorems
3: Complexity classes
4: Polynomial reduction
5: NP-complete problems
6: P and NP relationship, polynomial isomorphism
7: Randomized Computation
8: Approximation algorithms
9: PSPACE
10: Parallel computation
11: Counting classes
12: Cryptography
Textbooks and external materials
Ch. Papadimitriou:
Computational Complexity
(main source of information, online version of the book)
S.Arora, B.Barak:
Computational Complexity, a Modern Approach
(available as PDF online).
I.Černá:
Úvod do teórie zložitosti
(in Slovak language, textbook FI MU)
Reduction from SAT to CNF
(from pg. 14).
Other
RAM machine interpret
