0

Consider the function problem find_solution(input) -> output, and the decision problem solution_exists(input) -> yes_or_no. Is there any problem that is computable in its decision problem form, but not computable in its function problem form?

In other words, is there exist problems that you can algorithmically determine whether a solution exists, but you can't algoritmically know what the solution is?

ABu
  • 451
  • 2
  • 9
  • None that I know of specifically, though there are many problems where we can prove a solution exists, yet finding the solution is algorithmically “hard.” Take, for example, the problem of finding a 2logn clique in a random graph. Such a clique exists Whp, but best methods for finding it take n^2logn time. Ramsey numbers are another good example (we know they exist, but can’t compute them with current computing resources). Computing Nash equilibria in certain games is similar, so is computing the chromatic number of the sphere/ hyper cube for which we only know upper and lower bounds. – mm8511 Apr 07 '20 at 16:18
  • 1
    Just leaving a comment as I'm not sure this is what you are looking for: notice that the halting problem (determining whether a TM halts or not) satisfies your last question. Every problem has a solution, so yes, you can (algorithmically) determine whether a solution exists and no, you cannot find such solution algorithmically. – Manlio Apr 07 '20 at 16:58
  • @Malio I find your answer a bit tricky, but yeah you can determine whether a solution exists because the output domain is just {0, 1}, regarding the input, and that affects every decision problem. So you are proposing that, for every decision problem, you can define some kind of "metadecision problem" that would always returns yes. If that decision problem happens to be non-computable then it fits the conditions of my question. – ABu Apr 07 '20 at 17:54
  • @Peregring-lk yes pretty much. As long as every input has a solution (which you can prove non-computably), deciding whether the instance has a solution is trivial (the answer is always yes, no matter what the input is). Computing a solution is a different thing. – Manlio Apr 08 '20 at 00:25

1 Answers1

0

Notice that the set of all possible solutions to a problem expressible to a Turing Machine is a list of strings over some alphabet. That list can be ordered -- a common ordering is first by length, and then for those of the same length lexicographically relative to an ordering of the alphabet of the relevant Turing Machine.

What this means is, 

define find_solution(input) := 
   if solution_exists(input)
      then
         for s in ordered list of solution strings
            if s is a solution for input
               return("The solution is " + string(s) )
      else
        return("No solution exists.")

For inputs where a solution exists, we cannot a priori place a bound on the running time of the for loop over all possible solution strings. But, knowing that there is a solution in that list, we will eventually find it.

Eric Towers
  • 67,037
  • Great answer (I believe it), but it seems like it should be possible to break this by asking about a problem whose solution is not computable, but exists... (informally) something like “output the nth digit of the lexicographically first uncomputable number.” – mm8511 Apr 07 '20 at 16:58
  • Isn't that a circular argument? Because you are assuming that finding the set of all solution strings is computable. – ABu Apr 07 '20 at 17:48
  • Also I'm not sure if "checking if s is a solution" is granted to be computable even after you determined that the solution exists. – ABu Apr 07 '20 at 17:59
  • @mm8511 : If no algorithm can produce the $n^\text{th}$ digit, no algorithm can decide if the $n^\text{th}$ digit is a given, specific digit. But the hypothesis is that this is decidable, so each digit can be produced by the search I describe. For more on what being an uncomputable number means, I refer to the relevant discussion about Chaitin's constant. – Eric Towers Apr 07 '20 at 20:47
  • @Peregring-lk : The go-to computation model for all of these questions is Turing Machines. The computational subject of a Turing Machine is a language, a set of finite length strings over a finite alphabet. A decision problem asks some predicate about membership in the language (existence of any member -- nonempty language, membership of a given string, non-membership of a given string, membership of string with a given prefix, et c.) A solution is a finite string demonstrating that a given string satisfies the predicate and is in the language. Now search over all such demonstrations. – Eric Towers Apr 07 '20 at 20:53
  • @Peregring-lk : For more fun searching the space of demonstrations, see The 8000th Busy Beaver number eludes ZF set theory. – Eric Towers Apr 07 '20 at 20:58