2 added 9 characters in body
source | link

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
source | link

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