What is a counter example for this statement?

75 Views Asked by At

I know this is false, but I don't know any counter example for it:

For languages A and B, If A reduces to B, then B reduces to A.

1

There are 1 best solutions below

0
On

Here is a counter example consider two languages with the alphabet $\{0,1\}$.

$ A = (0|1)^* $ and $ B = 1 $.

There is a reduction function from A to B $f(w) = "1" $.

However we can't create a reduction function from B to A because there is no way to map a non word string in B (like $"0"$) into a nonword string of A because A doesn't have any nonword strings.