View source for Complexity Theory

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:

= 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.

[[Category: Computer Science]]