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?
3
$\begingroup$
$\endgroup$
-
$\begingroup$ Could you define what $\le_m$ means? $\endgroup$ – Jake Sep 14 '17 at 3:54
-
1$\begingroup$ many to one reductions $\endgroup$ – Link L Sep 14 '17 at 3:55
-
1$\begingroup$ A quick trivial example: $A = \{ n \}$ (all numbers), $B = \{ 2n \}$ (even numbers) $\endgroup$ – Vor Sep 14 '17 at 6:40
-
$\begingroup$ @Vor, how is this connected to many-one reductions? $\endgroup$ – rus9384 Sep 14 '17 at 6:40
-
1$\begingroup$ @rus9384: try to find a many-one-reduction from $B \to A$ ... how do you map the number $3 \notin B$? $\endgroup$ – Vor Sep 14 '17 at 6:42
4
$\begingroup$
$\endgroup$
I post my comment, as an extended note, which shows a small "formal trick".
A trivial example over natural numbers $\mathbb{N} = \{n > 0 \}$, is:
$A = \{ n\} = \mathbb{N}$ and $B = \{2n \}$ (even numbers).
According to the definition of many-one reduction: a many-one reduction from $B$ to $A$ is a total computable function $f : \mathbb{N} → \mathbb{N}$ that has the property that each $x$ is in $B$ if and only if $f(x)$ is in $A$.
Clearly we have $A \leq_m B$: a many-one reduction that works is $f(x) = 2$
But $B \nleq_m A$ because given $x \notin B$ (e.g. $x = 3$) you cannot map it to a $f(x) \notin A$ because $A$ contains all elements.
5
$\begingroup$
$\endgroup$
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.
