Timeline for Is DSPACE(n) = DSPACE(1.5n)?
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 13, 2023 at 23:20 | comment | added | Eric Allender | For a careful argument along these lines, see this paper: sciencedirect.com/science/article/pii/S0022000077800421 In it, Seiferas fixes the number of tape symbols, and also the number of heads per tape. Theorem U-2-D (based on Theorem 5) gets a separation by increasing the space bound by a factor of 10, not 2. I'm not aware of anything that was published improving this bound. | |
| Dec 28, 2018 at 19:48 | vote | accept | Alexey Milovanov | ||
| Nov 22, 2018 at 20:38 | vote | accept | Alexey Milovanov | ||
| Dec 28, 2018 at 16:55 | |||||
| Nov 22, 2018 at 20:21 | answer | added | domotorp | timeline score: 9 | |
| Nov 22, 2018 at 9:00 | history | tweeted | twitter.com/StackCSTheory/status/1065530440444981250 | ||
| Nov 22, 2018 at 8:48 | comment | added | Alexey Milovanov | @Thomas Actually I want $1 + o(1)$ | |
| Nov 22, 2018 at 8:41 | comment | added | domotorp | Why do you think that the space-hierarchy theorem gives $2f(n)$? I suppose that you argue that we need $f(n)$ space for simulation and $\log_{|\Sigma|} |\Sigma|^{f(n)}$ space for counting the number of steps to avoid infinite loops. But in both cases we need to first mark the $f(n)$'th location on the tape (can be done since $f$ is space-constructible) and how would you do the marking? Your argument is OK if you assume that the machines are not allowed to write *'s, but otherwise some further complications are needed. | |
| Nov 22, 2018 at 1:09 | comment | added | Thomas Steinke | Any reason you are interested in $\frac32$? Would $1+\Omega(1)$ be equally interesting? | |
| Nov 21, 2018 at 23:00 | history | asked | Alexey Milovanov | CC BY-SA 4.0 |