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
\(\textbf{PP=RP}\) consequences
change probability in definition of PP
CircuitSat \(\in \) DTIME\((2^n)\) consequences
Prove/ Disprove
8
Determine if \(L\) in \(\mathcal{P}\)
Computational models & Complexity Cheat Sheet
Computational models & Complexity Cheat Sheet
Computational models & Complexity Cheat Sheet
By Saar Barak(
https://github.com/saarbk
)
