[Solved]: complexity of decision problems vs computing functions

Problem Detail: 

This is an area that admittedly I've always found subtle about CS and occasionally trips me up, and clearly others. recently on tcs.se a user asked an apparently innocuous question about N-Queens being NP hard, But it got downvoted there & goes unanswered because the audience felt it was poorly phrased.

The issue seems to be that some questions in CS have to be phrased as decision problems to measure their complexity, and it is not always obvious how to do that. also other questions are studied from the POV(point of view) of computing a function with integer or string inputs and outputs, in which case eg their time or space complexity can be studied. for some NP complete problems e.g. SAT its proven that the decision problem (e.g. determining whether an answer exists) is roughly equivalent in time/space complexity to solving the function problem (finding a satisfying assignment), but of course that's not always the case.

Moreover much of CS theory is focused on NP complete problems [esp that presented to undergraduates in textbooks], which are nec. decision problems, which might lead to a mistaken impression that other types of problem formats are not as central to the theory. Also NP complete is sometimes shown in a hierarchy that includes other complexity classes such as PSpace which can be used to measure function complexity in addition to decision complexity.

Think that the N-Queens example question & related comments also shows that a bunch of related questions about the same problem in this case N-Queens can vary widely/dramatically in their complexity depending on slight variations of the phrasing. e.g. in this case:

• Is there a solution to the N-Queens problem on a $n \times n$ chessboard? this problem turns out to have O(1) time complexity— the answer is always Y.
• What is the complexity of finding a solution to the N-Queens problem given $n$ as the input referring to a square $n \times n$ chessboard? as that question notes in comments by Peter Shor, an advanced and subtle thm from CS called "mahaney's" thm applies because it might refer to a "sparse input". also JeffE found a paper that says its in P.
• There is an NP complete or NP hard version of this problem if the squares are irregularly specified as the input. i.e. some kind of input that specifies the square allowed/unallowed locations (haven't looked up the details).

---

While advanced theorists may find all this verging on trivial, feel its a legitimate area of focus which sometimes gets glossed over in theoretical treatments. my question

Is there a reference somewhere that points/sorts out these kinds of subtleties/difficulties in formulating CS problems?

It would be helpful if it also talks about how the issue relates to the complexity hierarchy. know that this is covered in some textbooks, but even then haven't seen a nice concise discussion of that and wonder if anyone has a favorite ref for this type of issue. (suppose Garey and Johnson might have some discussion of this although don't have a copy close to check.)

Am not specifically focused on the N-Queens problem with this question, but an answer that sketches out the distinctions wrt N-Queens might be helpful. [eg an expanded explanation of Shor's comment how Mahaneys thm applies, the irregular board construction input format, etc]

fyi here are two other example problems Ive noticed that can vary widely in complexity depending on various restrictions on the input

1 Post correspondence problem. it can go from undecidable to NP complete or even in P depending on various restrictions on the solution.

[2] Finding whether a regular expression is equivalent to all strings over the alphabet. with squaring this was shown to be in ExpSpace by Stockmeyer/Meyer, but restrictions on length lead to it to being in NP complete or P. see e.g. Chee Yap, Intro to Complexity classes, ch5 on complete problems.

Asked By : vzn

Answered By : Vor

A quick highlight to underline how easily the time complexity of a function problem (calculate $f(x)$) can differ from the time complexity of the corresponding decision problem (is $f(x)=^?y$).

If we take $f(x) = 2^x$, then in order to calculate $f(x)$ we need exponential time, but the corresponding decision problem $\{ (x,y) | f(x)=y \}$ is trivially in $P$ (given $x$ and $y$ just check that $y$ is a 1 followed by $x$ 0s).

The difference between search and decision is underlined (and explained) in many books and a lot of information can also be found online.

For example given an $NP$ problem, it is obvious that if you can quickly find a solution then you can quickly answer if the problem has a solution or not; hence the decision problem reduces to the search problem in $O(1)$. But the question: "Does search reduce in polynomial time to decision?" is more subtle. It is easy to prove that if you have an oracle for $SAT$ then you can solve in polynomial (linear) time the corresponding search problem: if the formula is not satisfiable then output undefined, else for each variable $x_i$, set it to true and call the oracle, if the formula is not satisfiable then set $x_i$ to false (this technique is called self-reducibility).

It turns out that this result can be extended to all $NP$-complete problems.

But for problems that are not $NP$-complete, under a complexity assumption ($EE \neq NEE$), there is a language in $NP$ for which search does not reduce to decision (see "The Complexity of Decision versus Search").

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4667