Some Reduction Inferences - Revision history

Arjun Suresh at 09:47, 14 July 2014

2014-07-14T09:47:08Z

Arjun Suresh at 18:21, 23 February 2014

2014-02-23T18:21:46Z

Arjun Suresh at 17:55, 4 January 2014

2014-01-04T17:55:16Z

Arjun Suresh at 17:54, 4 January 2014

2014-01-04T17:54:57Z

Arjun Suresh at 17:53, 4 January 2014

2014-01-04T17:53:57Z

Arjun Suresh: /* Somethings to take care of */

2013-12-31T16:57:15Z

‎Somethings to take care of

Arjun Suresh: /* Somethings to take care of */

2013-12-31T16:55:51Z

‎Somethings to take care of

Arjun Suresh at 16:51, 31 December 2013

2013-12-31T16:51:48Z

Arjun Suresh at 16:44, 31 December 2013

2013-12-31T16:44:06Z

Arjun Suresh: /* Somethings to take care of */

2013-12-31T16:43:19Z

‎Somethings to take care of

← Older revision		Revision as of 09:47, 14 July 2014
Line 33:		Line 33:


−		+	[[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 18:21, 23 February 2014
Line 37:		Line 37:

	[[Category:Notes & Ebooks for GATE Preparation]]		[[Category:Notes & Ebooks for GATE Preparation]]
		+
		+	[[Category: Compact Notes for Reference of Understanding]]

@@ Line 3: / Line 3: @@
 [[NP,_NP_Complete,_NP_Hard | P, NP, NPC, NPH]]
-*<math>P</math> is a subset of <math>NP</math>, but whether <math>P = NP</math> is  still not known.
+*<math>P</math> is a subset of <math>NP</math>, but whether <math>P = NP</math> is  still not known
 *<math>NPC</math> is a subset of <math>NP</math> (only if <math>P \neq NP</math>, <math>NPC</math> is a proper subset of <math>NP</math>)
 *<math>NPC</math> is a proper subset of <math>NPH</math>

@@ Line 1: / Line 1: @@
 <metadesc>Reduction to|from P, NP, NPC and NP-Hard problems</metadesc>
-*<math>P</math> is a subset of <math>NP</math>, but whether <math>P = NP</math>  still not known.
+[[NP,_NP_Complete,_NP_Hard | P, NP, NPC, NPH]]
-*<math>NPC</math> is a subset of <math>NP</math> (if <math>P \neq NP</math>, then only <math>NPC</math> is a proper subset of <math>NP</math>)
 *<math>NPC</math> is a proper subset of <math>NPH</math>
 ==Reduction==
 Reducing a problem <math>A</math> to problem <math>B</math> means converting an instance of problem <math>A</math> to an instance of problem <math>B</math>. Then, if we know the solution of problem <math>B</math>, we can solve problem <math>A</math> by using it.

← Older revision		Revision as of 17:53, 4 January 2014
Line 1:		Line 1:
	<metadesc>Reduction to\|from P, NP, NPC and NP-Hard problems</metadesc>		<metadesc>Reduction to\|from P, NP, NPC and NP-Hard problems</metadesc>
		+
		+	*<math>P</math> is a subset of <math>NP</math>, but whether <math>P = NP</math> still not known.
		+	*<math>NPC</math> is a subset of <math>NP</math> (if <math>P \neq NP</math>, then only <math>NPC</math> is a proper subset of <math>NP</math>)
		+	*<math>NPC</math> is a proper subset of <math>NPH</math>

	$P \subseteq NP \subseteq NPC \subseteq NPH$		$P \subseteq NP \subseteq NPC \subseteq NPH$

@@ Line 22: / Line 22: @@
 **Here, we cannot say <math>A</math> is <math>NPC</math>. All we can say is <math>A</math> cannot be harder than <math>NPC</math> and hence <math>NP</math> (all <math>NPC</math> problems are in <math>NP</math>). To belong to <math>NPC</math>, all <math>NP</math> problems must be reducible to <math>A</math>, which we cannot guarantee from the given statement.
 *If <math>A</math> is reduced to <math>B</math>, <math>C</math> is reduced to <math>A</math> ,  <math>B \in NP </math> and  $C \in$ <math>NPC</math>, then <math>A</math> $\in$ <math>NPC</math>
-**Here, the first reduction says that <math>A</math> is in <math>NP</math>. The second reduction says that all <math>NP</math> problems can be reduced to <math>A</math> (because <math>C</math> is in <math>NPC</math>, by definition of <math>NPC</math>, all problems in <math>NP</math> are reducible to <math>C</math> and now <math>C</math> is reduced to <math>A</math>). Hence, the two sufficient conditions for <math>NPC</math> are satisfied and <math>A</math> is in <math>NPC</math>
+**Here, the first reduction says that <math>A</math> is in <math>NP</math>. The second reduction says that all <math>NP</math> problems can be reduced to <math>A</math> (because <math>C</math> is in <math>NPC</math>, by definition of <math>NPC</math>, all problems in <math>NP</math> are reducible to <math>C</math> and now <math>C</math> is reduced to <math>A</math>). Hence, the two necessary and sufficient conditions for <math>NPC</math> are satisfied and <math>A</math> is in <math>NPC</math>
 *If <math>A</math> is reduced to <math>B</math> and <math>B</math> $\in$ $NPH$, then <math>A</math> $\in$ <math>?</math>
 **Here we can't say anything about <math>A</math>. It can be as hard as <math>NPH</math>, or as simple as <math>P</math>.

← Older revision		Revision as of 16:51, 31 December 2013
Line 1:		Line 1:
		+	<metadesc>Reduction to\|from P, NP, NPC and NP-Hard problems</metadesc>
		+
	$P \subseteq NP \subseteq NPC \subseteq NPH$		$P \subseteq NP \subseteq NPC \subseteq NPH$