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.)

  • 2
    $\begingroup$ This claim is philosophical rather than mathematical, so it cannot be correct or incorrect; it is a matter of opinion. In order to be able to treat it seriously, you will need to define the concepts involved, in this case "computational problem", "decision version", "computational difficulty" and "roughly equal". $\endgroup$ – Yuval Filmus Aug 5 '17 at 9:11
  • 2
    $\begingroup$ If you find the Demaine's comment confusing, I suggest ignoring it rather than philosophizing about it. $\endgroup$ – Yuval Filmus Aug 5 '17 at 9:12

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.

  • 2
    $\begingroup$ I agree with your answer, but just a note: in my opinion linear time and loglinear time fall in the "roughly equal computational difficulty" :-) $\endgroup$ – Vor Aug 5 '17 at 19:10

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.

A.Arora, B. Barak, "Computational Complexity A Modern Approach", 2009, pg. 28.

  • $\begingroup$ This is a precious answer because it points to a very interesting read. However, neither the answer nor (for the amount I was able to read currently) the suggested book actually answer the asked question fully. It would be more useful to add if the quoted observation can lead to the conclusion that not all problems can be expressed as decision problems. However, elaborating on the the quoted chapter title, the answer is probably that "it does not matter". $\endgroup$ – alexlomba87 Jun 8 '20 at 19:41

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).

  • $\begingroup$ Can you explain in 'Sort Problem' how you define $f$, range of $f$, domain of $f$, $n$ and $L$? $\endgroup$ – H.H Aug 4 '17 at 15:54
  • $\begingroup$ I think 'Sort Problem' is not a function form $N$ to $N$. $\endgroup$ – H.H Aug 4 '17 at 15:55
  • $\begingroup$ @H.H. do you mean 'Search problems'? $\endgroup$ – Vor Aug 4 '17 at 15:55
  • $\begingroup$ 'Sort Problem': Consider $n$ numbers $\sigma = N_{1},...N_{n}$. A sort algorithm is a function with domain $\sigma$ and it's range is the monotonic order of $\sigma$'s elements. $\endgroup$ – H.H Aug 4 '17 at 16:08
  • 2
    $\begingroup$ @DavidRicherby: you're right, there are many hard search problems with easy decision version (see for example cstheory.stackexchange.com/q/1848/3247) but probably the statement in the Demaine's lecture is referred to optimization problems, indeed after the claim he writes: "Maximization/minimization problems: binary search on bound b to find optimal". Nevertheless I should edit my answer because in this version it is rather rough. $\endgroup$ – Vor Aug 4 '17 at 19:23

Your Answer

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

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