There exists problems that cannot be solved fast. Complexity theory is the classification of problems into classes.

P: Set of problems for which exists an algorithm that solves it in poly time O(n^k).
NP: Set of problems for which there exists an algorithm that, given an instance of the problem and a certificate (simple solution), verifies the solution in poly time
- Example: K-independent set
NP complete: Set of problems in NP that are the hardest problems in that set
- Example. SAT problem: Given a boolean equation, find whether there is an input such that the equation returns true.

Independent Set Problem

Consider a graph G(V,E). Find the largest set of vertices such that they do not share edges.

Approach: Brute Force

For all possible subsets of V, if they are independent, set max.