0x0f0f0f - Alessandro Cheli

Computability Theory and Complexity Theory Cheat Sheet

Published 29 December 2020

Tags: #maths, #computability, #complexity, #algorithms

I made these two posters containing computability theory and complexity theory basic knowledge, theorems and short intuitive proofs. Although this is meant for an undergraduate computer science course, I hope these will result useful for anybody interested in the subject.

You can find the source code in the Github Repository. Please open an issue if you find any mistake or typo!

Click on the images to download the PDF file!

Computability Theory Cheat Sheet

Complexity Theory Cheat Sheet