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?

  • $\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

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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.