- P = set of decision problems that can be solved on a deterministic machine in polynomial time
- Solutions are easy to find
- NP = set of problems that can be solved on a non-deterministic machine in polynomial time
- Hard to solve, easy to verify
- Co-NP = "no" answer can be given in polynomial time on a non-deterministic machine
- NP-hard = takes a long time to check whether the solution is correct
- NP-complete = NP and NP-hard