GATE CSE 2003 | Question: 52

Question

Consider two languages $L_1$ and $L_2$ each on the alphabet $\Sigma$. Let $f : \Sigma^* \to \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

Comments

in option b, every p problem is np ?? please explain the relation here, how can NP be P, as considered.

for option (d) it is clear recursive enumerable is tm decidable and recursive languages are tm recognisable, so both in a way are decidable. so it is correct.

but please explain option (b)

---

what does polynomial time bijection mean ?

---

Can someone explain the question in simpler form ....I am not getting Polynomial time Bijection .

---

We have one to one mapping for all instances of L1 to L2.

L1 is given to be undecidable ( for option c)

Further L1 is polynomial time reducible to L2. (By given mapping). Now if L2 is decidable then there is algorithm to solve L2 in polytime. But then we can solve every instance of L1 in polytime, making L1 also decidable. Contradiction

Answer 1

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.

Comments

@Arjun sir, how can a language be in p or np? it can either be decidable or undecidable based on acceptance by a tm? plus here, we are talking about functions taking input as one lang and generating output as other lang to be as polynomial time computable

---

@Arjun sir can you plz explain this

---

How is option B true ?

Answer 2

My hunch(backed up by some logic) says C as availability of such computable function that which can transform an element of Non-Re language to REC is not possible..

Comments

That logic is pretty good. Even though the question seems difficult, choices make this question easy :)

Answer 3

Because T always halts, T is an HTM.

 

Answer 4

L1 is polynomial time reducible to L2.
Now if L2 is decidable then L1 should also be decidable.

Hence, option (c) is wrong.

Answer 5

We are given two languages $ L_1 $ and $ L_2 $ over an alphabet $ \Sigma $, and a bijection $ f : \Sigma^* \to \Sigma^* $ satisfying:

• $ f $ is computable in polynomial time,
• $ f^{-1} $ is also computable in polynomial time,
• For every $ x \in \Sigma^* $,  

  $$
  x \in L_1 \iff f(x) \in L_2.
  $$

This means $ f $ is a polynomial-time isomorphism (or p-isomorphism) between $ L_1 $ and $ L_2 $. Such a mapping is a total, one-to-one, onto, and efficiently computable transformation that preserves membership. Consequently, $ L_1 $ and $ L_2 $ are computationally indistinguishable with respect to fundamental properties like decidability: any such property preserved under computable bijections with computable inverses must hold for both or for neither.

Option A: $ L_1 \in P $ and $ L_2 $ is finite

A finite language is always in $ P $, since membership can be decided by checking against a finite list. Because $ f $ is a bijection, $ L_1 $ is finite if and only if $ L_2 $ is finite. Thus, if $ L_2 $ is finite, then $ L_1 = f^{-1}(L_2) $ is also finite and therefore in $ P $. This scenario is consistent with the existence of a p-isomorphism.

Option A can be true.

---

Option B: $ L_1 \in \text{NP} $ and $ L_2 \in P $

Since $ P \subseteq \text{NP} $, any language in $ P $ is automatically in NP. If $ L_2 \in P $, then to decide $ L_1 $, we can compute $ f(x) $ in polynomial time and run the polynomial-time decider for $ L_2 $. This gives a polynomial-time algorithm for $ L_1 $, so $ L_1 \in P \subseteq \text{NP} $. Thus, the condition $ L_1 \in \text{NP} $ is satisfied. There is no contradiction here.

Option B can be true.

---

Option C: $ L_1 $ is undecidable and $ L_2 $ is decidable

This is impossible.

Assume $ L_2 $ is decidable. Then there exists a Turing machine $ M_2 $ that halts on every input and correctly decides $ L_2 $. To decide $ L_1 $, construct a machine $ M_1 $ that, on input $ x $:

1. Computes $ y = f(x) $ (possible in finite time, as $ f $ is computable),
2. Runs $ M_2 $ on $ y $,
3. Accepts if $ M_2 $ accepts, and rejects otherwise.

Because $ x \in L_1 \iff f(x) \in L_2 $, this procedure correctly decides $ L_1 $, and $ M_1 $ always halts (since both $ f $ and $ M_2 $ halt). Hence, $ L_1 $ is decidable. The reverse also holds: if $ L_1 $ is decidable, then $ L_2 $ is decidable using $ f^{-1} $. Therefore, decidability is preserved under such a bijection. It is logically impossible for one language to be undecidable while the other is decidable.

Option C cannot be true.

---

Option D: $ L_1 $ is recursively enumerable and $ L_2 $ is recursive

Recall that a recursive (decidable) language is always recursively enumerable, but the converse is not always true. The statement only asserts that $ L_1 $ is recursively enumerable and $ L_2 $ is recursiveit does not claim that $ L_1 $ is not recursive. In fact, if $ L_2 $ is recursive, then $ L_1 $ must also be recursive (by the same construction used in Option C). Since every recursive language is recursively enumerable, the condition “$ L_1 $ is recursively enumerable” is satisfied.

Thus, this scenario is consistent for example, when both languages are decidable.

Option D can be true.

 

$$
\color{lime} \boxed{\text{Answer: C}}
$$

Comments

can explain how u take  x∈L1⟺f(x)∈L2x∈L1​⟺f(x)∈L2???

bcz in question

(∀x)[x∈L1if (x)∈L2]

i.e (x if p)==   p=> x???

OR can i miss some information ..i.e is there due to BIJECTION u can write like that..

can u explain?

 

---

The question mentions $\texttt{iff}$ which means if and only if ( that basically is a bijection). Now $x\leftrightarrow  y$ is $x \rightarrow y$ and $y \rightarrow x$

so u just apply cases such that we can prove either of the side false if u cant its true . Hope thats helps.

Answer 6

The correct answer is C.

This statement CANNOT be true.

 

The problem describes a polynomial-time reduction that works in both directions.

1. What the setup means:

   • The function $f$ is a computable, halting algorithm. The condition $x \in L_1 \text{ iff } f(x) \in L_2$ means we can use a solution for $L_2$ to solve $L_1$.

   • This is the definition of a reduction, $L_1 \le L_2$. It means "$L_1$ is no harder than $L_2$."

2. Why C is impossible:

   • Let's assume $L_2$ is decidable, as the option states. This means there is an algorithm (a Turing machine that always halts) that can correctly answer "yes" or "no" for any input $y$ in $L_2$.

   • Now, let's build an algorithm to decide $L_1$:

     1. For any input string $x$, first compute $y = f(x)$. The problem states $f$ is "polynomial time computable," which means this step is an algorithm that is guaranteed to halt.

     2. Next, feed the resulting string $y$ into the decider for $L_2$.

     3. Since the $L_2$ decider is guaranteed to halt, it will give a "yes" or "no" answer.

     4. Our algorithm for $L_1$ returns this answer.

   • This procedure creates a decider for $L_1$—an algorithm that always halts and gives the correct answer.

   • This proves that if $L_2$ is decidable, $L_1$ must also be decidable.

   • The Contradiction: Option C states that $L_1$ is undecidable and $L_2$ is decidable. This is a direct logical contradiction. If $L_2$ is decidable, $L_1$ must be decidable. Therefore, this scenario cannot be true.

---

 

Why the Other Options Can Be True

 

• A. $L_1 \in P$ and $L_2$ is finite: A finite language is in $P$. If $L_2 \in P$, and $L_1$ is poly-time equivalent to $L_2$, $L_1$ would also be in $P$. This is consistent.

• B. $L_1 \in NP$ and $L_2 \in P$: If $L_2 \in P$, then $L_1$ must also be in $P$. Since $P$ is a subset of $NP$ ($P \subseteq NP$), $L_1$ is also in $NP$. This is perfectly consistent.

• D. $L_1$ is recursively enumerable and $L_2$ is recursive: "Recursive" is just another word for "Decidable." "Recursively Enumerable" (RE) means partially decidable. As we just proved, if $L_2$ is Decidable, $L_1$ must also be Decidable. Every Decidable language is also RE. This is perfectly consistent.