Complexity Theory - Revision history

Rice at 01:09, 13 March 2024

2024-03-13T01:09:54Z

← Older revision		Revision as of 01:09, 13 March 2024
Line 3:		Line 3:
	* 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, given an instance of the problem and a certificate (simple solution), 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:		** 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 =

Rice at 00:33, 13 March 2024

2024-03-13T00:33:21Z

← Older revision		Revision as of 00:33, 13 March 2024
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:

	= Independent Set Problem =		= Independent Set Problem =

Rice: 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..."

2024-03-13T00:31:29Z

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

New page

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.

[[Category: Computer Science]]