patternMinor
Examples of sets $A$ and $B$ such that $A \leq_m B$ but not $B \leq_m A$
Viewed 0 times
suchleq_mbutexamplesthatandsetsnot
Problem
I know that such sets exist and they are called sets that are not m-complete, but I am not sure how to find them. Can someone give examples?
Solution
Let $A$ be a computable set of all even nonnegative integers, and $H$ be the language of the Halting problem. Assume also that $w_1 \in H$ and $w_2 \notin H$. Then define a mapping as following:
$$f(x) = w_1 \text{ if } x \text{ is even}, w_2 \text{ if } x \text{ is odd } $$
This function is clearly computable and $x$ is even iff $f(x) = w_1 \in H$, i.e., $A \leq_m H$. However, $H \nleq_m A$, otherwise $H$ would be computable/recursive.
$$f(x) = w_1 \text{ if } x \text{ is even}, w_2 \text{ if } x \text{ is odd } $$
This function is clearly computable and $x$ is even iff $f(x) = w_1 \in H$, i.e., $A \leq_m H$. However, $H \nleq_m A$, otherwise $H$ would be computable/recursive.
Context
StackExchange Computer Science Q#81198, answer score: 5
Revisions (0)
No revisions yet.