Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Questions > Let A ≤m B denotes that language A is m...
Start Learning for Free
Let A ≤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?
- a)If A ≤m B and B is recursive then A is recursive.
- b)If A ≤m B and A is undecidable then B is undecidable.
- c)If A ≤m B and B is recursively enumerable then A is recursively enumerable.
- d)If A ≤m B and B is not recursively enumerable then A is not recursively enumerable.
Correct answer is option 'D'. Can you explain this answer?
| FREE This question is part of | Download PDF Attempt this Test |
Verified Answer
Let A ≤m B denotes that language A is mapping reducible (also kn...
- 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
Please comment below if you find anything wrong in the above post.
Most Upvoted Answer
Let A ≤m B denotes that language A is mapping reducible (also kn...
False Statement: If A m B and B is not recursively enumerable then A is not recursively enumerable.
Explanation:
To understand why this statement is false, let us first define what it means for a language to be mapping reducible (many-to-one reducible) to another language.
Mapping Reducibility:
A language A is said to be mapping reducible to another language B (denoted by A m B) if there exists a computable function f such that for every input x:
- If x is in A, then f(x) is in B.
- If x is not in A, then f(x) is not in B.
Now let us examine the options one by one to see why the given statement is false.
a) If A m B and B is recursive then A is recursive.
This statement is true. If A is mapping reducible to B and B is recursive (decidable), then A can also be decided using the same reduction function. This means that if we have an algorithm to decide B, we can use the reduction function to transform any instance of A into an instance of B and use the algorithm to decide A as well.
b) If A m B and A is undecidable then B is undecidable.
This statement is true. If A is mapping reducible to B and A is undecidable, then B must also be undecidable. This is because if we have an algorithm to decide B, we can use the reduction function to transform any instance of A into an instance of B and use the algorithm to decide A as well, which contradicts the fact that A is undecidable.
c) If A m B and B is recursively enumerable then A is recursively enumerable.
This statement is true. If A is mapping reducible to B and B is recursively enumerable, then we can construct a Turing machine that enumerates all the strings in B. We can use the reduction function to map each string in A to a string in B and output it if it is in A. This way, we can effectively enumerate all the strings in A, making A recursively enumerable.
d) If A m B and B is not recursively enumerable then A is not recursively enumerable.
This statement is false. Just because B is not recursively enumerable does not imply that A is also not recursively enumerable. The mapping reducibility does not preserve the property of recursive enumerability. A language can be mapping reducible to a non-recursively enumerable language and still be recursively enumerable.
Therefore, the false statement is option D.
Explanation:
To understand why this statement is false, let us first define what it means for a language to be mapping reducible (many-to-one reducible) to another language.
Mapping Reducibility:
A language A is said to be mapping reducible to another language B (denoted by A m B) if there exists a computable function f such that for every input x:
- If x is in A, then f(x) is in B.
- If x is not in A, then f(x) is not in B.
Now let us examine the options one by one to see why the given statement is false.
a) If A m B and B is recursive then A is recursive.
This statement is true. If A is mapping reducible to B and B is recursive (decidable), then A can also be decided using the same reduction function. This means that if we have an algorithm to decide B, we can use the reduction function to transform any instance of A into an instance of B and use the algorithm to decide A as well.
b) If A m B and A is undecidable then B is undecidable.
This statement is true. If A is mapping reducible to B and A is undecidable, then B must also be undecidable. This is because if we have an algorithm to decide B, we can use the reduction function to transform any instance of A into an instance of B and use the algorithm to decide A as well, which contradicts the fact that A is undecidable.
c) If A m B and B is recursively enumerable then A is recursively enumerable.
This statement is true. If A is mapping reducible to B and B is recursively enumerable, then we can construct a Turing machine that enumerates all the strings in B. We can use the reduction function to map each string in A to a string in B and output it if it is in A. This way, we can effectively enumerate all the strings in A, making A recursively enumerable.
d) If A m B and B is not recursively enumerable then A is not recursively enumerable.
This statement is false. Just because B is not recursively enumerable does not imply that A is also not recursively enumerable. The mapping reducibility does not preserve the property of recursive enumerability. A language can be mapping reducible to a non-recursively enumerable language and still be recursively enumerable.
Therefore, the false statement is option D.
Attention Computer Science Engineering (CSE) Students!
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Similar Computer Science Engineering (CSE) Doubts
Top Courses for Computer Science Engineering (CSE)View all
Let A ≤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?a)If A ≤m B and B is recursive then A is recursive.b)If A ≤m B and A is undecidable then B is undecidable.c)If A ≤m B and B is recursively enumerable then A is recursively enumerable.d)If A ≤m B and B is not recursively enumerable then A is not recursively enumerable.Correct answer is option 'D'. Can you explain this answer?
Question Description
Let A ≤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?a)If A ≤m B and B is recursive then A is recursive.b)If A ≤m B and A is undecidable then B is undecidable.c)If A ≤m B and B is recursively enumerable then A is recursively enumerable.d)If A ≤m B and B is not recursively enumerable then A is not recursively enumerable.Correct answer is option 'D'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Let A ≤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?a)If A ≤m B and B is recursive then A is recursive.b)If A ≤m B and A is undecidable then B is undecidable.c)If A ≤m B and B is recursively enumerable then A is recursively enumerable.d)If A ≤m B and B is not recursively enumerable then A is not recursively enumerable.Correct answer is option 'D'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Let A ≤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?a)If A ≤m B and B is recursive then A is recursive.b)If A ≤m B and A is undecidable then B is undecidable.c)If A ≤m B and B is recursively enumerable then A is recursively enumerable.d)If A ≤m B and B is not recursively enumerable then A is not recursively enumerable.Correct answer is option 'D'. Can you explain this answer?.
Let A ≤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?a)If A ≤m B and B is recursive then A is recursive.b)If A ≤m B and A is undecidable then B is undecidable.c)If A ≤m B and B is recursively enumerable then A is recursively enumerable.d)If A ≤m B and B is not recursively enumerable then A is not recursively enumerable.Correct answer is option 'D'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Let A ≤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?a)If A ≤m B and B is recursive then A is recursive.b)If A ≤m B and A is undecidable then B is undecidable.c)If A ≤m B and B is recursively enumerable then A is recursively enumerable.d)If A ≤m B and B is not recursively enumerable then A is not recursively enumerable.Correct answer is option 'D'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Let A ≤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?a)If A ≤m B and B is recursive then A is recursive.b)If A ≤m B and A is undecidable then B is undecidable.c)If A ≤m B and B is recursively enumerable then A is recursively enumerable.d)If A ≤m B and B is not recursively enumerable then A is not recursively enumerable.Correct answer is option 'D'. Can you explain this answer?.
Solutions for Let A ≤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?a)If A ≤m B and B is recursive then A is recursive.b)If A ≤m B and A is undecidable then B is undecidable.c)If A ≤m B and B is recursively enumerable then A is recursively enumerable.d)If A ≤m B and B is not recursively enumerable then A is not recursively enumerable.Correct answer is option 'D'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE).
Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of Let A ≤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?a)If A ≤m B and B is recursive then A is recursive.b)If A ≤m B and A is undecidable then B is undecidable.c)If A ≤m B and B is recursively enumerable then A is recursively enumerable.d)If A ≤m B and B is not recursively enumerable then A is not recursively enumerable.Correct answer is option 'D'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
Let A ≤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?a)If A ≤m B and B is recursive then A is recursive.b)If A ≤m B and A is undecidable then B is undecidable.c)If A ≤m B and B is recursively enumerable then A is recursively enumerable.d)If A ≤m B and B is not recursively enumerable then A is not recursively enumerable.Correct answer is option 'D'. Can you explain this answer?, a detailed solution for Let A ≤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?a)If A ≤m B and B is recursive then A is recursive.b)If A ≤m B and A is undecidable then B is undecidable.c)If A ≤m B and B is recursively enumerable then A is recursively enumerable.d)If A ≤m B and B is not recursively enumerable then A is not recursively enumerable.Correct answer is option 'D'. Can you explain this answer? has been provided alongside types of Let A ≤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?a)If A ≤m B and B is recursive then A is recursive.b)If A ≤m B and A is undecidable then B is undecidable.c)If A ≤m B and B is recursively enumerable then A is recursively enumerable.d)If A ≤m B and B is not recursively enumerable then A is not recursively enumerable.Correct answer is option 'D'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice Let A ≤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?a)If A ≤m B and B is recursive then A is recursive.b)If A ≤m B and A is undecidable then B is undecidable.c)If A ≤m B and B is recursively enumerable then A is recursively enumerable.d)If A ≤m B and B is not recursively enumerable then A is not recursively enumerable.Correct answer is option 'D'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
|
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Suggested Free Tests
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup