This chapter introduces classical complexity classes (P, NP, BPP) and the quantum class BQP, motivating quantum speedups while grounding expectations. The discussion begins with basic computational problems and the specific structure of decision problems. Problems are then categorized into classical complexity classes P, NP, and NP-hard, based on the conjectured computational power and resource requirements of the computational model that can solve them efficiently. Further complexity classes are defined, and the conjectured relation between classical and quantum complexity classes is presented. A concluding thought experiment links information theory to thermodynamics.