3
$\begingroup$

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?

$\endgroup$
9
  • $\begingroup$ Could you define what $\le_m$ means? $\endgroup$
    – Jake
    Sep 14, 2017 at 3:54
  • 1
    $\begingroup$ many to one reductions $\endgroup$
    – Link L
    Sep 14, 2017 at 3:55
  • 1
    $\begingroup$ A quick trivial example: $A = \{ n \}$ (all numbers), $B = \{ 2n \}$ (even numbers) $\endgroup$
    – Vor
    Sep 14, 2017 at 6:40
  • $\begingroup$ @Vor, how is this connected to many-one reductions? $\endgroup$
    – rus9384
    Sep 14, 2017 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, 2017 at 6:42

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
0

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.