5
$\begingroup$

We know all optimisation problems can be converted to decision problems. Is that true for search problems, counting problems and function problems as well? Description of the types of problems is given here: Computational problem.

Edit: So, the comments suggest that I state more precisely what I mean. I'm not entirely sure how to do that, so I'll tell you where I'm coming from. I understand that a Turing machine can solve only decision problems (It can accept or reject a string). I am wondering if a Turing machine can solve all kinds of problems - which is why I ask, can all those types of problems be expressed as decision problems?

A better way to put it would probably be, can all those types of problems be expressed in a way that they might be solved by a Turing machine?

$\endgroup$
  • 2
    $\begingroup$ What do you mean by "convert"? How should the original and "converted" problem relate to each other? $\endgroup$ – Raphael May 29 '18 at 16:47
  • $\begingroup$ As in, can I map every problem to a decision problem (or a bunch of decision problems) such that when I solve the decision problem, it is trivial to get the solution of the original problem? $\endgroup$ – Mahathi Vempati May 29 '18 at 16:57
  • 1
    $\begingroup$ Please include your definition into post via edit. I think that a bit more strict definition of such mapping would be nice. $\endgroup$ – Evil May 29 '18 at 17:01
  • 1
    $\begingroup$ Related: Is there a generic procedure to produce hard enough decision problems? $\endgroup$ – Discrete lizard May 29 '18 at 17:24
  • 1
    $\begingroup$ "I understand that a Turing machine can solve only decision problems" That's simply not true. One can perfectly well define a TM to compute a function, where the output of the function is taken to be the contents of the non-blank portion of the tape at termination. Or a nondeterministic TM can be taken as defining a function $\Sigma^*\to\mathbb{N}$ defined as the number of accepting paths. And probably plenty of other similar definitions exist. $\endgroup$ – David Richerby Jun 1 '18 at 12:53

Your Answer

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

Browse other questions tagged or ask your own question.