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)$?


1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.