GATE2003 q52 - Revision history

Arjun Suresh at 18:50, 8 September 2014

2014-09-08T18:50:03Z

Arjun Suresh at 11:22, 15 July 2014

2014-07-15T11:22:01Z

Arjun Suresh at 09:43, 7 July 2014

2014-07-07T09:43:30Z

Arjun Suresh at 07:05, 15 April 2014

2014-04-15T07:05:49Z

Arjun Suresh at 14:04, 14 April 2014

2014-04-14T14:04:19Z

Arjun Suresh: /* Solution */

2013-12-15T21:34:34Z

‎Solution

Arjun Suresh at 21:33, 15 December 2013

2013-12-15T21:33:52Z

Arjun Suresh at 21:32, 15 December 2013

2013-12-15T21:32:45Z

Arjun Suresh at 21:31, 15 December 2013

2013-12-15T21:31:59Z

Arjun Suresh: /* Solution */

2013-12-15T21:25:43Z

‎Solution

@@ Line 3: / Line 3: @@
 Which of the following '''CANNOT''' be true ?
-(A) <math>L_1</math> $\in P$ and <math>L_2</math> is finite
+(A) $L_1$ $\in P$ and $L_2$ is finite
-(B) <math>L_1</math> $\in NP$ and <math>L_2</math> $\in P$
+(B) $L_1$ $\in NP$ and $L_2$ $\in P$
-'''(C) <math>L_1</math> is undecidable and <math>L_2</math> is decidable'''
+'''(C) $L_1$ is undecidable and $L_2$ is decidable'''
-(D) <math>L_1</math> is recursively enumerable and <math>L_2</math> is recursive
+(D) $L_1$ is recursively enumerable and $L_2$ is recursive
 ==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
-  Since, <math>f</math> is a polynomial time computable bijection and <span class="nocode" style="color:#48484c"> $f^{-1}$ </span> is also polynomial time computable, $L_1$ and $L_2$ should have the same complexity (isomorphic). This is because, given a problem for $L_1$, we can always do a polynomial time reduction to $L_2$ and vice verse. Hence, the answer is 'C', as in 'A', $L_1$ and $L_2$ can be finite, in 'B', $L_1$ and $L_2$ can be in $P$ and in 'D', $L_1$ and $L_2$ can be recursive. Only, in 'C' there is no intersection for $L_1$ and $L_2$, and hence it canʼt be true.
+  Since, $f$ is a polynomial time computable bijection and <span class="nocode" style="color:#48484c"> $f^{-1}$ </span> is also polynomial time computable, $L_1$ and $L_2$ should have the same complexity (isomorphic). This is because, given a problem for $L_1$, we can always do a polynomial time reduction to $L_2$ and vice verse. Hence, the answer is 'C', as in 'A', $L_1$ and $L_2$ can be finite, in 'B', $L_1$ and $L_2$ can be in $P$ and in 'D', $L_1$ and $L_2$ can be recursive. Only, in 'C' there is no intersection for $L_1$ and $L_2$, and hence it canʼt be true.
 Alternatively, we can prove 'C' to be false as follows:

← Older revision		Revision as of 11:22, 15 July 2014
Line 24:		Line 24:

	[[Category: GATE2003]]		[[Category: GATE2003]]
−	[[Category: Automata questions]]	+	[[Category: Automata questions from GATE]]

← Older revision		Revision as of 09:43, 7 July 2014
Line 24:		Line 24:

	[[Category: GATE2003]]		[[Category: GATE2003]]
−	~~[[Category: Automata Theory]]~~
	[[Category: Automata questions]]		[[Category: Automata questions]]

@@ Line 25: / Line 25: @@
 [[Category: GATE2003]]
 [[Category: Automata Theory]]
-[[Category: Previous year GATE questions]]
+[[Category: Automata questions]]

@@ Line 11: / Line 11: @@
 (D) <math>L_1</math> is recursively enumerable and <math>L_2</math> is recursive
-===Solution===
+==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
   Since, <math>f</math> is a polynomial time computable bijection and <span class="nocode" style="color:#48484c"> $f^{-1}$ </span> is also polynomial time computable, $L_1$ and $L_2$ should have the same complexity (isomorphic). This is because, given a problem for $L_1$, we can always do a polynomial time reduction to $L_2$ and vice verse. Hence, the answer is 'C', as in 'A', $L_1$ and $L_2$ can be finite, in 'B', $L_1$ and $L_2$ can be in $P$ and in 'D', $L_1$ and $L_2$ can be recursive. Only, in 'C' there is no intersection for $L_1$ and $L_2$, and hence it canʼt be true.

← Older revision		Revision as of 21:34, 15 December 2013
Line 16:		Line 16:

	Alternatively, we can prove 'C' to be false as follows:		Alternatively, we can prove 'C' to be false as follows:
−	Given $L_2$ is decidable. Now, for a problem in $L_1$, we can have a $TM$, which takes an input x, calculates <span class="nocode" style="color:~~black~~">$f(x)$ </span>in polynomial time, check <span class="nocode" style="color:~~black~~">$f(x)$ </span> is in $L_2$ (this is decidable as $L_2$ is decidable), and if it is, then output yes and otherwise no. Thus $L_1$ must also be decidable.	+	Given $L_2$ is decidable. Now, for a problem in $L_1$, we can have a $TM$, which takes an input x, calculates <span class="nocode" style="color:#48484c">$f(x)$ </span>in polynomial time, check <span class="nocode" style="color:#48484c">$f(x)$ </span> is in $L_2$ (this is decidable as $L_2$ is decidable), and if it is, then output yes and otherwise no. Thus $L_1$ must also be decidable.

@@ Line 13: / Line 13: @@
 ===Solution===
-  Since, <math>f</math> is a polynomial time computable bijection and <span class="nocode" style="color:red"> $f^{-1}$ </span> is also polynomial time computable, $L_1$ and $L_2$ should have the same complexity (isomorphic). This is because, given a problem for $L_1$, we can always do a polynomial time reduction to $L_2$ and vice verse. Hence, the answer is 'C', as in 'A', $L_1$ and $L_2$ can be finite, in 'B', $L_1$ and $L_2$ can be in $P$ and in 'D', $L_1$ and $L_2$ can be recursive. Only, in 'C' there is no intersection for $L_1$ and $L_2$, and hence it canʼt be true.
+  Since, <math>f</math> is a polynomial time computable bijection and <span class="nocode" style="color:black"> $f^{-1}$ </span> is also polynomial time computable, $L_1$ and $L_2$ should have the same complexity (isomorphic). This is because, given a problem for $L_1$, we can always do a polynomial time reduction to $L_2$ and vice verse. Hence, the answer is 'C', as in 'A', $L_1$ and $L_2$ can be finite, in 'B', $L_1$ and $L_2$ can be in $P$ and in 'D', $L_1$ and $L_2$ can be recursive. Only, in 'C' there is no intersection for $L_1$ and $L_2$, and hence it canʼt be true.
 Alternatively, we can prove 'C' to be false as follows:
-  Given $L_2$ is decidable. Now, for a problem in $L_1$, we can have a $TM$, which takes an input x, calculates <span class="nocode">$f(x)$ </span>in polynomial time, check <span class="nocode">$f(x)$ </span> is in $L_2$ (this is decidable as $L_2$ is decidable), and if it is, then output yes and otherwise no. Thus $L_1$ must also be decidable.
+  Given $L_2$ is decidable. Now, for a problem in $L_1$, we can have a $TM$, which takes an input x, calculates <span class="nocode" style="color:black">$f(x)$ </span>in polynomial time, check <span class="nocode" style="color:black">$f(x)$ </span> is in $L_2$ (this is decidable as $L_2$ is decidable), and if it is, then output yes and otherwise no. Thus $L_1$ must also be decidable.

← Older revision		Revision as of 21:25, 15 December 2013
Line 16:		Line 16:

	Alternatively, we can prove 'C' to be false as follows:		Alternatively, we can prove 'C' to be false as follows:
−	Given $L_2$ is decidable. Now, for a problem in $L_1$, we can have a $TM$, which takes an input x, calculates <span class="nocode">$f(x)$ </span>in polynomial time, check $f~~(~~x\)$ is in $L_2$ (this is decidable as $L_2$ is decidable), and if it is, then output yes and otherwise no. Thus $L_1$ must also be decidable.	+	Given $L_2$ is decidable. Now, for a problem in $L_1$, we can have a $TM$, which takes an input x, calculates <span class="nocode">$f(x)$ </span>in polynomial time, check <span class="nocode">$f(x)$ </span> is in $L_2$ (this is decidable as $L_2$ is decidable), and if it is, then output yes and otherwise no. Thus $L_1$ must also be decidable.