Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 13: | Line 13: | ||
===Solution=== | ===Solution=== | ||
| − | Since, <math>f</math> is a polynomial time computable bijection and <math>f</math> <math>f^{-1}</math> 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 <math>f^1</math> <math>f^{-1}</math> 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: | ||
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
GATECSESince, <math>f</math> is a polynomial time computable bijection and <math>f^1</math> <math>f^{-1}</math> 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> $\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
Since, <math>f</math> is a polynomial time computable bijection and <math>f</math> <math>f^{-1}</math> 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.