0
$\begingroup$

We know that every optimisation problem has an equivalent decision problem.

So say I keep going up a mountain (I.e. I am maximising my altitude) following a certain number of finite steps (similarly to a TM). Is that enough to assert that I am solving a decision problem?

If yes which one?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Also related. $\endgroup$
    – Raphael ♦
    Sep 4, 2016 at 10:20
  • 2
    $\begingroup$ And not, stating a maximization problem and calling it decision problem doesn't make it one. $\endgroup$
    – Raphael ♦
    Sep 4, 2016 at 10:21
  • $\begingroup$ @Raphael Well let me give you my version. In my example I am maximising my altitude by synthetically checking where my next step can lead me. Once that's done I take the step which produces the largest positive change in altitude. That's a decision problem and it looks like I can generalise this process leading me to believe that indeed every optimisation problem can be seen as a decision problems like shown by CS theory. Anything wrong with my reasoning? $\endgroup$
    – Jerome
    Sep 4, 2016 at 15:04
  • 1
    $\begingroup$ You are not using "decision problem" in the way we do in TCS. We don't mean "decide where to go" but "decide between yes and no". $\endgroup$
    – Raphael ♦
    Sep 4, 2016 at 18:44
  • $\begingroup$ @Raphael I am. I am searching for the maximum altitude using a yes/no method $\endgroup$
    – Jerome
    Sep 4, 2016 at 19:30

0

Reset to default