Timeline for Can more polynomial time compensate for less polynomial memory?
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 23, 2018 at 23:59 | answer | added | Timothy Chow | timeline score: 4 | |
| Jan 23, 2018 at 23:41 | comment | added | Timothy Chow | @FrankWaaldijk : When Dan says that we won't be able to prove it, I think he just means that humanity is currently too stupid and ignorant to prove such a thing. | |
| Jan 18, 2018 at 8:37 | history | edited | Franka Waaldijk | CC BY-SA 3.0 |
update to summarize comments and references
|
| Jan 17, 2018 at 11:18 | comment | added | Franka Waaldijk | @DanBrumleve: yes, but that partly justifies the intuition for specifying $s>2$. The iteration then stops way before reaching your $\epsilon>0$ situation. also, i disagree that things like P=PSPACE are clearly impossible to (dis)prove. that would imply that they are independent of PA, which may be true but then i would like to see some arguments for this. I've added more thoughts on chat...cheers Frank | |
| Jan 13, 2018 at 18:22 | comment | added | Dan Brumleve | Actually, that implies $\text{P} \neq \text{PSPACE}$ already, by the space hierarchy theorem, so we won't be able to prove it. At best we could have some restricted version like $\text{DTIME}(n^k) \subseteq \text{DTISP}(n^{O(1)}, n^{f(k)})$ with $\liminf_{k \rightarrow \infty} f(k) = \infty$. I'll incorporate these comments into my answer after thinking this over a little more. | |
| Jan 13, 2018 at 5:24 | comment | added | Dan Brumleve | Another observation which supports Timothy Chow's claim that this problem is hard: if we had $\text{DTISP}(n^a, n^b) = \text{DTISP}(n^{2 \cdot a}, n^{\frac{b}{2}})$ for all $a, b$ in some model, by iterating it we would obtain that for all $\epsilon > 0$, $\text{P} \subseteq \text{DTISP}(n^{O(1)}, n^{\epsilon})$. That is really close to $\text{P} \subseteq \text{DTISP}(n^{O(1)}, n^{o(1)})$ which implies $\text{P} \neq \text{PSPACE}$. | |
| Jan 12, 2018 at 9:54 | comment | added | Franka Waaldijk | I'm chatting with Dan Brumleve on this subject (see the link in the comments below the answer below), but I'm pressed for time right now and can only continue after the weekend... | |
| Jan 12, 2018 at 9:42 | comment | added | Franka Waaldijk | @TimothyChow: thanks for your comment. It surprises me a bit, since I've tried to pose this question in a really natural way. People discuss things like whether NP=PSPACE, which seems much harder and far less natural by comparison (and also P=L (see below) which is more natural but also harder). Anyway, if there are so few results on questions like this one, then that would for me be interesting as well, so if you do think of any reference please let me know. I think that some time-memory trade-off theory (model-invariant) is minimally required to get a grasp on computational complexity. | |
| Jan 11, 2018 at 19:33 | comment | added | Timothy Chow | Nothing like this is known for general computations, although I'm not sure I could back up this claim with a reference since it's so far beyond the current frontier of knowledge that people don't usually discuss it. A useful keyword for you may be DTISP, which is used for complexity classes that are simultaneously time-bounded and space-bounded. | |
| Jan 10, 2018 at 0:12 | comment | added | Franka Waaldijk | Don't worry, I'm also quite good in misreading :-) and I'm sure your remark helps other people to understand the question better. | |
| Jan 10, 2018 at 0:05 | comment | added | LSpice | Sorry, you're quite right; I read "polynomial-time $\mathrm O(n^{s/2})$" even though you had clearly written "polynomial-space $\mathrm O(n^s)$". | |
| Jan 9, 2018 at 23:44 | answer | added | Dan Brumleve | timeline score: 11 | |
| Jan 9, 2018 at 21:29 | comment | added | Franka Waaldijk | The compensating algorithm gets more time, not less. So your remark doesn't immediately help me see why a memory-rich polytime algorithm cannot be mimicked by a less memory-rich but time-richer polytime algorithm. Or am I missing something obvious? | |
| Jan 9, 2018 at 20:46 | comment | added | LSpice | Surely the answer to this is 'no', because some problems have, say, $\Omega(n^3)$ lower bounds on their time complexity regardless of space usage? | |
| Jan 9, 2018 at 20:29 | history | asked | Franka Waaldijk | CC BY-SA 3.0 |