Timeline for Is there a formal definition of sub-instances or sub-problems?
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 30, 2020 at 14:56 | vote | accept | Blanco | ||
| Oct 30, 2020 at 14:56 | vote | accept | Blanco | ||
| Oct 30, 2020 at 14:56 | |||||
| Oct 20, 2020 at 6:51 | comment | added | Discrete lizard♦ | I think this is a good illustration of why we don't formalize this notion in practice. I have one nitpick: if $y$ is a subinstance of $x$ (in the sense that $y$ is used to solve $x$), then $y$ does not necessarily have to be smaller in terms of string length. Suppose we have a DP table $T[x,y,z]$, indexed by 3 variables. Then it is possible that e.g. $T[0,2,2]$ is a subinstance of $T[1,0,0]$, while $(0,2,2)$ is longer than $(1,0,0)$ in a reasonable encoding. So, for your definition to be general enough, you'll probably need a problem specific measure of instance size. | |
| Oct 20, 2020 at 1:36 | history | answered | NaturalLogZ | CC BY-SA 4.0 |