General Question

Does the space hierarchy theorem generalize to non-uniform computation?

Here are a few more specific questions:

  • Is $L/poly \subsetneq PSPACE/poly$?

  • For all space constructible functions $f(n)$, is $DSPACE(o(f(n)))/poly \subsetneq DSPACE(f(n))/poly$?

  • For what functions $h(n)$ is it known that: for all space constructible $f(n)$, $DSPACE(o(f(n)))/h(n) \subsetneq DSPACE(f(n))/h(n)$?


One non-uniform "space hierarchy" that we can prove is a size hierarchy for branching programs. For a Boolean function $f: \{0, 1\}^n \to \{0, 1\}$, let $B(f)$ denote the smallest size of a branching program computing $f$. By an argument analogous to this hierarchy argument for circuit size, one can show that there are constants $\epsilon, c$ so for every value $b \leq \epsilon \cdot 2^n / n$, there is a function $f: \{0, 1\}^n \to \{0, 1\}$ such that $b - cn \leq B(f) \leq b$.

I think separating $\mathbf{PSPACE}/\text{poly}$ from $\mathbf{L}/\text{poly}$ would be difficult. It's equivalent to proving that some language in $\mathbf{PSPACE}$ has super-polynomial branching program complexity. A simple argument shows that $\mathbf{PSPACE}$ does not have fixed-polynomial-size branching programs:

Proposition. For every constant $k$, there is a language $L \in \mathbf{PSPACE}$ so that for all sufficiently large $n$, $B(L_n) > n^k$. (Here $L_n$ is the indicator function for $L \cap \{0, 1\}^n$.)

Proof. By the hierarchy we proved, there is a branching program $P$ of size $n^{k + 1}$ that computes a function $f$ with $B(f) > n^k$. In polynomial space, we can iterate over all branching programs of size $n^{k + 1}$, all branching programs of size $n^k$, and all inputs of length $n$ to find such a branching program $P$. Then we can simulate $P$ to compute $f$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.