Skip to main content
10 votes

Are space and time hierarchies even comparable?

You can get the situation you describe by choosing weird functions $f(n)$ and $g(n)$. For example, let $g(n) = n^3$ and $$f(n) = \begin{cases} n & \text{if $n$ is odd}, \\\ 2^{n^5} & \text{...
Mikhail Rudoy's user avatar
9 votes

Lower bound on pebbling numbers

A full proof (based on superconcentrators) can be found in chapter 24 "The pebble game" of the book Uwe Schöning and Randall Pruim: Gems of Theoretical Computer Science Springer, 1998 ...
Gamow's user avatar
  • 5,772
7 votes

Conesequences of $\forall k\in \mathbb N \space NP\not\subseteq TISP(poly(n),n^k)$

This would imply that L⊊NP since L⊆TISP(poly(n),n^k) k∈N
Avi Tal's user avatar
  • 1,606
6 votes

Lower bound on pebbling numbers

Not sure whether I am missing something, but... The Omega(n/log n) lower bound is from: [PTC77] Wolfgang J. Paul, Robert Endre Tarjan, and James R. Celoni. Space bounds for a game on graphs. ...
Jakob Nordstrom's user avatar
2 votes

What is known about computing distinct count range queries?

A sketch data structure is an approximation of a set of elements. Sketches vary in what they store -- some store just hashes, some store elements from the set (a sample), and some store floating-point ...
jbapple's user avatar
  • 11.2k
2 votes

Counting reversibly using few FullAdders and little work space

Here is a construction with $3N + O(\lg N)$ adder computations/uncomputations and $2 \lg(N)$ ancilla usage. Divide the input into $N/\lg N$ groups of size $\lg N$. Allocate a result register of size $...
Craig Gidney's user avatar
  • 1,518
1 vote

Are space and time hierarchies even comparable?

In some sense yes, specifically as of right now we have that: $\textbf{DTIME}(S(n)) \subseteq \textbf{SPACE}(S(n)) \subseteq \textbf{NSPACE}(S(n)) \subseteq \textbf{DTIME}(2^{O(S(n))})$ And also we ...
CurryKatsuCutlet's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible