Det grundläggande målet inom komplexitetsteorin är att klassificera problem med avseende på hur mycket resurser som krävs för att lösa dem. Komplexitetsklasser är klasser av problem som i något avseende kräver "lika" mycket resurser för att lösa. De mest grundläggande resurserna som studeras är beräkningstid och minnesutrymme. Ett fullständigt problem för en komplexitetsklass är ett problem som kan ses som det svåraste inom klassen.
Följande områden behandlas: Komplexitetsklasserna L, NL, P, NP, PSPACE, etc. Reduktion och fullständighet. Cooks' sats. Approximerbarhet. Probabilistiska algoritmer. Interaktiva bevis (IP).