2 added 9 characters in body edited Sep 22 '12 at 20:10 Vor 10.4k11 gold badge2323 silver badges5454 bronze badges 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"). 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 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"). 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"). 1 answered Sep 22 '12 at 20:05 Vor 10.4k11 gold badge2323 silver badges5454 bronze badges 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 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").