Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Undecidability
Let A ≤ p B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B in polynomial time. Which one of the following is True?
1
If A ≤ p B and B is Recursive then A is also Recursive
2
If A ≤ p B and B is decidable then A is also decidable
3
If A ≤ p B and B is undecidable then A is also undecidable
4
If A ≤ p B and B is NP problem then A is also NP problem