3
$\begingroup$

Let:

  • f be a decidable decision problem.
  • g be an undecidable decision problem.

I refered to those rules:

  • If $f$ reduces to $g$ and $g$ is decidable $\implies$ $f$ will be decidable.
  • If $f$ reduces to $g$ and $f$ is not decidable $\implies$ $g$ will be not decidable.

Questions:

1) It may be possible to reduce $f$ to $g$. But why?

Reducing $f$ to $g$ means to reduce decidable to undecidable. If I take a look at these rules the outcome of the implication will always be true and the "implier" will always be false because of the end - so $f$ might be reduced to $g$.

2) It is definitely not possible to reduce g to f. Why?

Reducing $g$ to $f$ means to reduce undecidable to decidable. If I take a look at these rules the outcome of the implication will always be false and the second part of the and of the "implier" will be true, therefore the reduction MUST be false.

Are my thoughts correct? Overall: When can you reduce two decidability problems?

$\endgroup$

closed as too broad by D.W. Jan 25 '16 at 21:52

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Welcome to CS.SE! 1. What specifically is your question? I count about 5 sentences that end in a question mark. Which question are you asking us to answer? We ask that you only ask one question per post, please. Also, we discourage "please check whether my answer is correct" questions. Can you edit your question to clarify what you are asking and to address this feedback? I'm going to put this on hold to give you a chance to edit the question, but once these issues are addressed this can be re-opened. 2. Can you define the meaning of the $\propto$ notation in your post? $\endgroup$ – D.W. Jan 25 '16 at 21:52