Difference between revisions of "GATE2003 q52"

 
(22 intermediate revisions by the same user not shown)
Line 3: Line 3:
 
Which of the following '''CANNOT''' be true ?
 
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
  
−
===Solution===
+
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
  
−
  Since, <math>f</math> is a polynomial time computable bijection and $f^{-1}$ 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:
 
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 $f(x)$ 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" 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.  
−
$t$ $g^2$
+
 
  
 
{{Template:FBD}}
 
{{Template:FBD}}
Line 24: Line 24:
  
 
[[Category: GATE2003]]
 
[[Category: GATE2003]]
−
[[Category: Automata Theory]]
+
[[Category: Automata questions from GATE]]
−
[[Category: Previous year GATE questions]]
 

Latest revision as of 18:50, 8 September 2014

Consider two languages $L_1$ and $L_2$ each on the alphabet $\Sigma$. Let $f : \Sigma → \Sigma$ be a polynomial time computable bijection such that $(\forall x) [ x\in L_1$ iff $f(x) \in L_2]$. Further, let $f^{-1}$ be also polynomial time computable.

Which of the following CANNOT be true ?

(A) $L_1$ $\in P$ and $L_2$ is finite

(B) $L_1$ $\in NP$ and $L_2$ $\in P$

(C) $L_1$ is undecidable and $L_2$ is decidable

(D) $L_1$ is recursively enumerable and $L_2$ is recursive

Solution by Arjun Suresh

Since, $f$ is a polynomial time computable bijection and  $f^{-1}$  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 $f(x)$ 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.




blog comments powered by Disqus
Retrieved from "https://gatecse.in/w/index.php?title=GATE2003_q52&oldid=4237"

Consider two languages $L_1$ and $L_2$ each on the alphabet $\Sigma$. Let $f : \Sigma → \Sigma$ be a polynomial time computable bijection such that $(\forall x) [ x\in L_1$ iff $f(x) \in L_2]$. Further, let $f^{-1}$ be also polynomial time computable.

Which of the following CANNOT be true ?

(A) <math>L_1</math> $\in P$ and <math>L_2</math> is finite

(B) <math>L_1</math> $\in NP$ and <math>L_2</math> $\in P$

(C) <math>L_1</math> is undecidable and <math>L_2</math> is decidable

(D) <math>L_1</math> is recursively enumerable and <math>L_2</math> is recursive

Solution[edit]

Since, <math>f</math> is a polynomial time computable bijection and $f^{-1}$ 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 $f(x)$ 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. 
$t$ $g^2$




blog comments powered by Disqus