The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+26 votes

Let $A\:\leq_m\:B$ denotes that language $A$ is mapping reducible (also known as many-to-one reducible) to language $B$. Which one of the following is FALSE?

- If $A\: \leq_m B$ and $B$ is recursive then $A$ is recursive.
- If $A\: \leq_m B$ and $A$ is undecidable then $B$ is undecidable.
- If $A\: \leq_m B$ and $B$ is recursively enumerable then $A$ is recursively enumerable.
- If $A\: \leq_m B$ and $B$ is not recursively enumerable then $A$ is not recursively enumerable.

+26 votes

Best answer

+1

RE and undecidability are not same. RE implies semidecidable. A semidecidable problem could be: a decidable problem if its complement is also semidecidable or it can be undecidable if it's complement is not semidecidable. Undecidable languages are not recursive languages, but sometimes, they may be recursively enumerable languages. (Think complement of halting problem, it is non re and undecideable). Hope this helps.

0

**Please help me understand this kind of ques: **

For the given ques., If we say that **"undecidibility", "not recursive" and "not RE", etc., are the negetive characteristics** and **opposite of it is positive characteristic** for a language, and "A <m B" means that B is more harder than A,

then, can it be a sort of rule that to prove negetive characteristic, A should be known and B becomes the same, and for positive B should be known and A becomes the same.

for eg. if A <m B and A is undecidable then B is undecidable. (negetive)

If A ≤m B and B is recursively enumerable then A is recursively enumerable.(positive)

similerly, If A ≤m B and B is not recursively enumerable then it doesnt guarantee that A is not recursively enumerable, as we had to prove a negetive characteristic but instead of A, B was known.

Please tell me if it works in general or not.

Also positive - negetive is used just for differentiating.

0

when I read it first, I thought its perfect. But later I found something is odd here. Out of 4 observations which you have made in each category, first two seems to be going good with the venn dig. but when it comes to 3rd and 4th, I think we need to change the representation may be.

**if L is recursive then M may or may not be recursive**. This makes sense because there is RE language which may not be recursive.-------* (case 1)*

**if L is RE then M may or may not be RE**. this also make sense because set of languages is bigger than set of RE languages.

**if L is decidable then M may or may not be decidable.** How is that possible. M is a bigger set. If it is decidable, then how can anything inside this set can be undecidable. that means, if L is decidable then M can not be undecidable, so the other option left is decidable. In* case 1* recursive languages are also RE, but here a decidable language can not be undecidable at the same time.

similerly with 4th observation:

**if M is not recursive then L may or may not be recursive**. this looks right because here M could be RE and so L can also be RE, but not recursive.

**if M is not RE then L may or may not be RE**, again doesnt look good for same reason as described above. L is inner entity of M.

**if M is not decidable then L may or may not be decidable**. if M is not decidable and suppose L is decidable, then L is both decidable and undecidable at the same time.

But about your analogy regarding addition and multiplication, I cant really comment on it. It looks correct to me, but only if we dont represent it via venn diagram. I think if we consider that multiplication is made up of many additions, that is multiplication is derived from addition, then your analogy may suit it.

Let me know what do you think about it.

+2

A ≤m B implies that B is atleast as hard as A .

If B is easy then A is easy

If A is hard then B is hard

If B is hard then A may or may not be hard (Because B being hard does not garuntee A being hard)

If A is easy then B may or may not be easy (Because A being easy does not garuntee B being easy)

0

A reducible to B means A atmost as hard as B

Now A is undecidable, means A is RE, Then B must be atleast RE

Now A is undecidable, means A is RE, Then B must be atleast RE

0

RE IS SEMIDECIDABLE ?

AND IN SIMILAR MANNER B IS NOT RE BUT IT CAN BE OUTSIDE RE SO HOW CAN WE SAY A is not re we can reduce re to non re

AND IN SIMILAR MANNER B IS NOT RE BUT IT CAN BE OUTSIDE RE SO HOW CAN WE SAY A is not re we can reduce re to non re

+19 votes

0 votes

- A ≤m B means language A is mapping reducible to language B.Thus, A cannot be harder than B. Since, A can be reduced to B, instead of deciding A we can now decide B.
**So, the first three options are correct.** - As B is not recursively enumerable, it doesn't guarantee A is not recursively enumerable.Thus, if A ≤m B and B is not recursively enumerable then A is not recursively enumerable.
**Therefore, answer is D is correct**

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.5k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,079 questions

45,572 answers

132,068 comments

49,045 users