<p>One non-uniform "space hierarchy" that we can prove is a <strong>size hierarchy for branching programs</strong>. 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 <a href="https://cstheory.stackexchange.com/a/5115/34371">this hierarchy argument for circuit size</a>, 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$.</p>

<p>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 <em>fixed</em>-polynomial-size branching programs:</p>

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

<p>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) &gt; 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$.</p>

CC BY-SA 3.0
2018-01-22T17:07:56.683Z
2018-01-22T17:07:56.683Z
William Hoza
<blockquote>
  <p><strong>General Question</strong></p>
  
  <p>Does the space hierarchy theorem generalize to non-uniform
  computation?</p>
</blockquote>

<p>Here are a few more specific questions:</p>

<ul>
<li><p>Is $L/poly \subsetneq PSPACE/poly$?</p></li>
<li><p>For all space constructible functions $f(n)$, is $DSPACE(o(f(n)))/poly \subsetneq DSPACE(f(n))/poly$?</p></li>
<li><p>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)$?</p></li>
</ul>

<cc.complexity-theory><space-bounded><space-complexity><advice-and-nonuniformity><hierarchy-theorems>
Does the space hierarchy theorem generalize to non-uniform computation?
Michael Wehar
# Does the space hierarchy theorem generalize to non-uniform computation?

(Asked by: username_0 on 2018-01-20)

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

**Tags:** cc.complexity-theory, space-bounded, space-complexity, advice-and-nonuniformity, hierarchy-theorems

---

## 1 answers

### Answer by username_1 on 2018-01-22. Score: 7 | Accepted answer

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](https://cstheory.stackexchange.com/a/5115/34371), 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$.


---

