Is a limited (deterministic) space-time hierarchy theorem correct? For example, we have a limitation of $O(n^2)$ space then: can we find problems that can be solved in $O(n^k)$ time and $O(n^2)$ space, but that have no algorithms that run in time $O(n^{k-1})$ and $O(n^2)$ space?
$\begingroup$
$\endgroup$
1
asked Mar 15, 2018 at 17:54
-
1$\begingroup$ This is essentially a duplicate of cstheory.stackexchange.com/q/38675 $\endgroup$– Emil JeřábekMar 15, 2018 at 18:02
Add a comment
|