Complexity Theory
From Rice Wiki
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 verifies the solution in poly time
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.