1
$\begingroup$

Can all types of computational problems (search, counting, optimization...) be modeled as (sets of) decision problems? Rephrased: For every type of computational problem is there a set of decision problems that if you solve those problems you get the result of the original problem?

colloquially: can all types of questions you can ask a string be answered by (a series of) results from YES NO questions? So the game is: you are given a question about a string, you are allowed to ask the string only YES NO questions. The string responds with answers to your YES NO questions that are computable. Can you compose all the answers you receive to narrow in on THE SINGLE answer to the original question (not a spread of answers / not some result but with a probability attached)?

Decision problems can be modeled as word to language membership. On the surface, this only models the functions that go from f:{0,1} * -->1 not all the other types of functions. Some g: {0,1} * -->{0,1} * for example. But I have a feeling the answer could be yes...

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

Yes. Every computation problem can be viewed as computing a function $f:\{0,1\}^ \to \{0,1\}^*$: on input $x$, the algorithm outputs $f(x)$.

Here is a corresponding decision problem: given $x$ and $i$, determine whether the $i$th bit of $f(x)$ is 1. If you can solve that decision problem, you can solve the original computation problem.

(Strictly speaking, you also need a way to decide whether the length of $f(x)$ is $i$; that can be addressed by defining the decision problem as taking inputs $x,i,b$; if $b=0$, then the problem is to determine whether the $i$th bit of $f(x)$ is 1; if $b=1$, the problem is to determine whether the length of $f(x)$ is $i$.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Search problems do not have a unique answer. Then taking the bit graph is meaningless. $\endgroup$
    – Emil Jeřábek
    Mar 28, 2020 at 9:03
  • $\begingroup$ @EmilJeřábek If the solution is not unique, you can use the following decision problems, right? 1) Is there a solution whose first bit is 1? 2) Is there a solution whose first bit is [determined by first question] followed by 1? etc. $\endgroup$
    – integrator
    Mar 28, 2020 at 9:12
  • $\begingroup$ @eru-cs This will often have larger complexity than the original problem. $\endgroup$
    – Emil Jeřábek
    Mar 28, 2020 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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