Complexity Class

Definition. A complexity class is a set of decision problems: all the problems solvable within a given resource budget, where the budget is a function of the input length (an amount of time or memory) compared up to growth rate via Big-O.

The first class defined precisely is P, in Lecture 9, and Unit 3 lives among these classes.