View article

This chapter looks at the basics of computational complexity theory. We examine how to calibrate computation by measuring the amount of time and space a machine uses. We introduce polynomial time and polynomial space. We prove the hierarchy theorems and Blum's speedup theorem.