Timeline for Understanding the definition of reduction
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 12, 2015 at 8:59 | comment | added | Shelby Moore III | I understand the matching on one value (e.g. 'YES') of a boolean test suffices for defining subsetting for boolean problems, yet afaics that Wikipedia definition doesn't appear to be general enough to handle non-boolean problems. Rather we would need to write a definition with tuples on pairs of (input, output) e.g. (x, g(x)) ∈ B and (f(x), g(x)) ∈ A for the general case? | |
| Oct 4, 2012 at 15:36 | comment | added | Yuval Filmus | $f$ is not necessarily injective. Indeed, often the first step is to recognize some "easy" instances and then solve them directly by outputting some fixed YES or NO instance of $A$. | |
| Oct 4, 2012 at 15:35 | comment | added | Yuval Filmus | $x \in B$ iff $f(x) \in A$ doesn't mean the same as $f(B) = A$, for many reasons. First, $f(B) = A$ doesn't guarantee that $f(x) \notin A$ for $x \notin B$. Second, the image of $f$ doesn't have to be all of $A$, indeed this is rarely the case. An equivalent statement would be $f(B) \subseteq A$ and $f(\overline{B}) \subseteq \overline{A}$. | |
| Oct 4, 2012 at 11:43 | comment | added | Tim | Thanks, Yuval! Does x∈B iff f(x)∈A mean the same as f(B)=A? Is f not necessarily injective? | |
| Oct 4, 2012 at 11:42 | vote | accept | Tim | ||
| Oct 3, 2012 at 19:37 | comment | added | Yuval Filmus | @Tim (4) All problems are decision problems. That is, each input either satisfies the property or doesn't satisfy it. In complexity theory we also often consider optimization problem, in which the challenge is to optimize some quantity under some constraints. | |
| Oct 3, 2012 at 19:36 | comment | added | Yuval Filmus | @Tim (1) We think of each "problem" as a property of the input. The set corresponding to the problem consists of these inputs for which the property holds. (2) $\mathbb{N}$ can be identified as the set of finite strings over some finite alphabet $\Sigma$. For example, for $\Sigma=\{0,1\}$ you can take the encoding which drops the MSB of the binary encoding of the number. So $5$ would code 01 and $13$ would code 101. (3) A solution to a problem, in this context, is an algorithm for it, which decides whether the input satisfies the property given by the problem. [cont.] | |
| Oct 3, 2012 at 18:20 | comment | added | Joe | @Tim The syntax is similar to that used for languages. Here $x$ is an input, $B$ is "a decision problem" or "the set of inputs for which a correct algorithm for the decision problem outputs yes". | |
| Oct 3, 2012 at 14:36 | comment | added | Tim | (4) Does $x \in B$ iff $f(x) \in A$ mean the same as $f(B)=A$? Is $f$ not necessarily injective? | |
| Oct 3, 2012 at 14:25 | comment | added | Tim | (3) Do "a solution to a problem" and "an input for which the problem has answer YES" mean the same? (4) Are the problems in discussion some special kind of problems? | |
| Oct 3, 2012 at 14:19 | comment | added | Tim | Thanks! (1) when you wrote $x\in B$, do you treat $B$ as the set of solutions for problem B, and $x$ is one of the solution? (2) "members of NP are problems, in the guise of subsets of the set of natural numbers (or of the set of finite binary strings, which is the same). The subset specifies the set of inputs for which the problem has the answer YES." Do you mean a problem corresponds to a subset of $\mathbb{N}$ or of $\Sigma^*$ for some alphabet $\Sigma$, by the subset being a set of inputs for which the problem has answer YES? | |
| Oct 3, 2012 at 13:35 | history | answered | Yuval Filmus | CC BY-SA 3.0 |