-2
$\begingroup$

Prove/ Disprove:

  • For every nontrivial $A,B\in R$, $A\le_m B$
  • For every nontrivial $A,B\in RE$, $A\le_m B$

trivial set is the empty-set or $\Sigma^*$.

So basically the question is if for every two nontrivial sets there is a computable function from $A$ to $B$.

I'd be glad to get hint/guidance since I'm kinda stuck and not sure how to attack this problem.

Thanks.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We want to help you understand concepts, but just doing your exercise for you won't be helping you (or anyone else). We expect you to make a serious effort on your own before asking and show us in the question what you tried. Also, please ask only one question per question. $\endgroup$
    – D.W. ♦
    Commented Jun 14, 2015 at 6:06
  • 2
    $\begingroup$ Incidentally, you've been given this feedback before: 1, 2, 3, 4. $\endgroup$
    – D.W. ♦
    Commented Jun 14, 2015 at 6:11
  • $\begingroup$ FWIW, here's a duplicate with answers. $\endgroup$
    – Raphael
    Commented Jun 15, 2015 at 21:38

1 Answer 1

Reset to default
3
$\begingroup$

HINT:

Go again over the definition of reductions. The many-one reduction from $A$ to $B$ is a function $f: \Sigma^* \to \Sigma^*$ that satisfies:

  1. $f$ is complete (=defined on any input)
  2. $f$ is computable (hint, hint).
  3. $f$ is valid: $x\in A$ if and only if $f(x) \in B$.

The "non trivial" part means there exists $x \in A$ and $x' \notin A$, and more importantly - the same holds for $B$. Now it should be fairly easy for you to complete the answer of your question.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Got it. we choose $a\in B$ and $b\notin B$ and the rest is simple... $\endgroup$
    – Elimination
    Commented Jun 14, 2015 at 12:12

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