1 Algorithm Definition
2 Turing Machine
3 Turing Machines
4 Reductions
Boolean Circuit
Regular language
5 Classical Results
6 Complexity Classes
7 Theorems on Complexity of Turing Machines
Space complexity
Randomized
$PP=RP$ consequences
change probability in definition of PP
CircuitSat $\in$ DTIME $(2^{n})$ consequences
Prove/ Disprove
8 Determine if $L$ in $P$

Computational models & Complexity Cheat Sheet

Computational models & Complexity Cheat Sheet

Computational models & Complexity Cheat Sheet

By Saar Barak(https://github.com/saarbk)

Computational models & Complexity Cheat Sheet