Complexity Theory: Difference between revisions
From Rice Wiki
(Created page with "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 po...") |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 2: | Line 2: | ||
* P: Set of problems for which exists an algorithm that solves it in poly time O(n^k). | * 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 | * 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 = | = Independent Set Problem = | ||
Latest revision as of 01:09, 13 March 2024
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.
