Is the following claim correct?:
Every computational problem has a decision version of roughly equal computational difficulty.
If the above claim is correct, please give a reference for it.
(I find this pdf from Prof. E. Demaine, but he doesn't provide any references.)
Here is a "counterexample": sorting. The natural decision version of sorting is deciding whether a given array is sorted. Another natural decision version is given an array and a permutation, decide whether the permutation correctly records the sorted order of the array. In both cases, the "decision versions" can be solved in linear time, while sorting itself (in most models) requires loglinear time.
Here is another "counterexample": consensus. This is a classical problem in distributed computing. I'm not sure it has a "decision version".
The claim you are stating is not a mathematical claim; it's just a comment whose goal is to explain why in introductory classes we only consider decision problems. There are three reasons: First, decision problems can be used to analyze many other types of computational problems (though not all of them). Second, it has become conventional to consider only decision problems (for example P and NP are classes of decision problems). Third, introductory classes are introductory, and so their scope is limited.
In order to make the claim a mathematical claim (and so, potentially, right or wrong), you will need to define all the concepts involved; there might be several ways of doing it, resulting in different interpretations of the claim. Some interpretations will result in valid statements: for example, optimization problems have canonical decision problems, and to some extent the two kinds of problems are equivalent in complexity. Other interpretations might be more problematic, for example if they encompass my first counterexample. Another source of difficulty is computational problems like my second counterexample to which this entire paradigm seems inapplicable.
Lecturers often make such comments, and these are supposed to be helpful for you as a student. If you find one of these comments confusing, I think it's best to just ignore it. If you have access to the professor, you can discuss the matter with them, but otherwise just drop the matter.
Decision problems are too limited. Some computational problems are not easily expressed as decision problems. Indeed, we will introduce several classes in the book to capture tasks such as computing non-Boolean functions, solving search problems, approximating optimization problems, interaction, and more. Yet the framework of decision problems turn out to be surprisingly expressive, and we will often use it in this book.
Decision problems (checking whether an instance of a problem has a solution or not) and Search problems (actually finding a solution of an instance of a problem if it has one) are two sides of the same coin.
Suppose that you have a computable function $f : \mathbb{N} \to \mathbb{N}$.
Then you can easily convert it to a decision version using this language:
$L = \{ (x,n) \mid f(x) \leq n \}$
Clearly if you can solve the decision problem $(x,n) \in^? L$ you can compute $f(x)$ in $O(\log f(x))$ steps using a binary search.
Usually the equivalent decision problem is formulated in a manner that reflects the structure of the source problem; a well-known example is boolean satisfiability.
"Given a boolean formula $\varphi$ in $n$ variables $x_1, x_2, ..., x_n$ calculate a satisfying assignment if it exists"
This can be solved using the decision version: "Given a boolean formula $\varphi$, is it satisfiable?" (i.e. $\varphi \in^? SAT$)
You can start setting $x_1 = True$ and checking if $\varphi_{x_1=T}$ (the formula $\varphi$ in which all $x_1$ occurrences have been replace with $True$ is satisfiable). If the answer is $Yes$ ($\varphi_{x_1=T} \in SAT$) then set $x_1 = True$, $x_1 = False$ otherwise. Then continue with $x_2, x_3, ...$ up to $x_n$ and at the end you'll have a satisfying assignment, or the procedure will stop at some $x_i$ for which $\varphi_{...,x_i=T} \notin SAT$ and $\varphi_{...,x_i=F} \notin SAT$ (i.e. the formula is unsatisfiable).
