NP, NP Complete, NP Hard - Revision history

Arjun Suresh: /* NP Problems */

2015-09-17T16:40:11Z

‎NP Problems

2014-09-02T10:12:02Z

2014-09-02T10:06:09Z

2014-09-02T10:03:16Z

2014-07-14T09:46:28Z

2014-06-09T16:16:07Z

2014-06-09T15:08:49Z

‎NP Hard Problems (NPH)

2014-06-09T14:28:17Z

2014-06-09T14:25:52Z

2014-06-09T13:43:43Z

@@ Line 9: / Line 9: @@
 ==<math>NP</math> Problems==
-Some think <math>NP</math> as Non-Polynomial. But actually its Non-deterministic Polynomial time. i.e.; these problems can be solved in polynomial time by a non-deterministic Turing machine and hence can take up to exponential time (some problems can be solved in sub-exponential but super polynomial time) by a deterministic Turing machine. In other words these problems can be verified (if a solution is given, say if its correct or wrong) in polynomial time. Examples include all P problems. One example of a problem not in <math>P</math> but in <math>NP</math> is [https://en.wikipedia.org/wiki/Integer_factorization_problem Integer Factorization].
+Some think <math>NP</math> as Non-Polynomial. But actually it is [https://en.wikipedia.org/wiki/NP_(complexity) Non-deterministic Polynomial time]. i.e.; "yes" instances of these problems can be solved in polynomial time by a non-deterministic Turing machine and hence can take up to exponential time (some problems can be solved in sub-exponential but super polynomial time) by a deterministic Turing machine. In other words these problems can be verified (if a solution is given, say if it is correct or wrong) in polynomial time. Examples include all P problems. One example of a problem not in <math>P</math> but in <math>NP</math> is [https://en.wikipedia.org/wiki/Integer_factorization_problem Integer Factorization].
 ==<math>NP</math> Complete Problems<math>(NPC)</math>==

← Older revision		Revision as of 10:12, 2 September 2014
Line 1:		Line 1:
−	~~<math>x^2</math>~~<metadesc>NP Complete definition in simple terms. Differences between P, NP, NP Complete and NP Hard Problems</metadesc>	+	<metadesc>NP Complete definition in simple terms. Differences between P, NP, NP Complete and NP Hard Problems</metadesc>

← Older revision		Revision as of 10:06, 2 September 2014
Line 1:		Line 1:
−	<math>~~Insert formula here~~</math><metadesc>NP Complete definition in simple terms. Differences between P, NP, NP Complete and NP Hard Problems</metadesc>	+	<math>x^2</math><metadesc>NP Complete definition in simple terms. Differences between P, NP, NP Complete and NP Hard Problems</metadesc>

← Older revision		Revision as of 10:03, 2 September 2014
Line 1:		Line 1:
−	<metadesc>NP Complete definition in simple terms. Differences between P, NP, NP Complete and NP Hard Problems</metadesc>	+	<math>Insert formula here</math><metadesc>NP Complete definition in simple terms. Differences between P, NP, NP Complete and NP Hard Problems</metadesc>

← Older revision		Revision as of 09:46, 14 July 2014
Line 40:		Line 40:


		+	[[Category: Automata Theory Notes]]

−	~~[[Category: Automata Theory]]~~
−
−	~~[[Category:Notes & Ebooks for GATE Preparation]]~~

	[[Category: Compact Notes for Reference of Understanding]]		[[Category: Compact Notes for Reference of Understanding]]

← Older revision		Revision as of 16:16, 9 June 2014
Line 37:		Line 37:
	--[[User:Arjun\|Arjun]] ([[User talk:Arjun\|talk]]) 22:48, 16 November 2013 (UTC)		--[[User:Arjun\|Arjun]] ([[User talk:Arjun\|talk]]) 22:48, 16 November 2013 (UTC)

−	{{Template:FB}}	+	{{Template:FBD}}

−
−	~~<disqus/>~~

← Older revision		Revision as of 15:08, 9 June 2014
Line 22:		Line 22:


−	https://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/~~800px~~-P_np_np-complete_np-hard.svg.png	+	https://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/400px-P_np_np-complete_np-hard.svg.png

← Older revision		Revision as of 14:28, 9 June 2014
Line 1:		Line 1:
	<metadesc>NP Complete definition in simple terms. Differences between P, NP, NP Complete and NP Hard Problems</metadesc>		<metadesc>NP Complete definition in simple terms. Differences between P, NP, NP Complete and NP Hard Problems</metadesc>

−
−	~~<viewCounter>\|{{PAGENAMEE}}</viewCounter>~~

	It might be because of the name but many graduate students find it difficult to understand <math>NP</math> problems. So, I thought of explaining them in an easy way. (When explanation becomes simple, some points may be lost. So, please do refer standard text books for more information)		It might be because of the name but many graduate students find it difficult to understand <math>NP</math> problems. So, I thought of explaining them in an easy way. (When explanation becomes simple, some points may be lost. So, please do refer standard text books for more information)

@@ Line 1: / Line 1: @@
 <metadesc>NP Complete definition in simple terms. Differences between P, NP, NP Complete and NP Hard Problems</metadesc>
-<viewCounter>NP,_NP_Complete,_NP_Hard</viewCounter>
 <viewCounter>|{{PAGENAMEE}}</viewCounter>

@@ Line 2: / Line 2: @@
 <viewCounter>NP,_NP_Complete,_NP_Hard</viewCounter>
-<viewCounter>{{{{PAGENAMEE}}}}</viewCounter>
+<viewCounter>|{{PAGENAMEE}}</viewCounter>
 It might be because of the name but many graduate students find it difficult to understand <math>NP</math> problems. So, I thought of explaining them in an easy way. (When explanation becomes simple, some points may be lost. So, please do refer standard text books for more information)