Problems On Many-one Reducible

215 Views Asked by At

In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative computational difficulty of two problems.

we say that A is many-one reducible or m-reducible to B and write $ A \leq_{m} B $.

infact my question is how we can proof the following sentence is false?

If Set B is recursive then for each set A which $A \neq \emptyset $, $A \neq N$ (N = Natural Numbers), we have $ B \leq_{m} A $.

1

There are 1 best solutions below

2
On BEST ANSWER

if $B$ is recursive, then you have a recursive function $\chi_B$ such that $\chi_B(x)=1$ iff $x\in B$ else $\chi_B(x)=0$.

So from $\chi_B$, and for any set $A$ with $a\in A$ and $z\notin A$, you can compute the function $f$ such that $f(x)=a$ iff $x\in B$ else $f(x)=z$.

Using $f$, you can remark that $B\le_m A$. So the sentence is true as long as $A\neq\emptyset$ (for $a$ to exist) and $A\neq\mathbb N$ (for $z$ to exist).