Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| (41 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | 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. | + | 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 ? | Which of the following '''CANNOT''' be true ? | ||
| − | (A) | + | (A) $L_1$ $\in P$ and $L_2$ is finite |
| − | (B) | + | (B) $L_1$ $\in NP$ and $L_2$ $\in P$ |
| − | '''(C) | + | '''(C) $L_1$ is undecidable and $L_2$ is decidable''' |
| − | (D) | + | (D) $L_1$ is recursively enumerable and $L_2$ is recursive |
| − | === | + | ==={{Template:Author|Arjun Suresh|{{arjunweb}} }}=== |
| + | 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: | |
| + | 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. | ||
| − | |||
| − | + | {{Template:FBD}} | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
[[Category: GATE2003]] | [[Category: GATE2003]] | ||
| − | [[Category: Automata | + | [[Category: Automata questions from GATE]] |
| − | |||
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
GATECSESince, $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.
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> Image not present P and <math>L_2</math> is finite
(B) <math>L_1</math> Image not present NP and <math>L_2</math> Image not present 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
A language <math>L</math> is recursively enumerable (partially decidable), iff there is a Turing Machine <math>M</math>, which can enumerate all the strings of <math>L</math>.
So, suppose <math>L_2</math> is decidable. Now we have a <math>TM</math> <math>T</math>, which can enumerate all strings of <math>L_2</math>. For each of these strings <math>w</math>, we can find <math>x</math>, such that <math>f(x) = w</math>, using the function $f^{-1}$. Since $f^{-1}$ is bijective, it ensures that for each of the string <math>w</math> enumerated by <math>T</math>, we are getting a unique $f^{-1}(w)$ (because of one-one property of bijection) and we are guaranteed that we'll generate all strings of $L_1$ (because of "co-domain = range" property of bijection),. i.e.; we are actually enumerating all strings of <math>L_1</math>. Thus, we are getting a <math>TM</math> which is enumerating all strings of <math>L_1</math>, which means <math>L_1</math> should also be recursively enumerable (partially decidable).
Thus, if <math>L_2</math> is decidable, <math>L_1</math> will at-least be partially decidable.