<p>Denoting the class of functions computed by branching programs of size $f(n)$ by $\text{BP}(f)$,
the best known bound seems to be the trivial $\text{DSPACE}(S(n)) \subseteq \text{BP}(2^{O(S(n))})$.
This matches the known inclusions $\text{DSPACE}(\log n) = \text{L} \subseteq \text{L}/poly = \text{BP}(poly)$; if a better bound were known then I would expect it to have been noted by Razborov in his FCT 1991 survey (<a href="http://people.cs.uchicago.edu/%7Erazborov/files/fct.pdf" rel="nofollow">preprint</a>), or in Jukna's 2012 BFC textbook.</p>

CC BY-SA 3.0
2015-01-05T16:45:01.463Z
2015-01-05T16:45:01.463Z
András Salamon
<p>One of the most elemental result of relationship between boolean circuit size and polynomial uniform computation is Pippenger and Fishers simulation: <span class="math-container">$DTIME[T(n)]\subseteq SIZE[T(n)\log  T(n)]$</span>.</p>
<p>I want to consider the small branching program family simulating low space  computation.</p>
<blockquote>
<p>Question1: What is the best simulation bound <span class="math-container">$S_{1}(n)$</span> which is known at this moment such that <span class="math-container">$DSPACE [S(n)]\subseteq BP-SIZE[S_{1}(n)]$</span></p>
<p>Question2:What is the best time complexity bound as far as we know, for the function that <span class="math-container">$1^{n}\rightarrow $</span>a branching program in the Question 1.</p>
</blockquote>

<cc.complexity-theory><reference-request><circuit-complexity><space-bounded><space-complexity>
Low space computation and branching program
tenhu
# Low space computation and branching program

(Asked by: username_0 on 2014-03-08)

One of the most elemental result of relationship between boolean circuit size and polynomial uniform computation is Pippenger and Fishers simulation: $DTIME[T(n)]\subseteq SIZE[T(n)\log T(n)]$.

I want to consider the small branching program family simulating low space computation.

> Question1: What is the best simulation bound $S\_{1}(n)$ which is known at this moment such that $DSPACE [S(n)]\subseteq BP-SIZE[S\_{1}(n)]$
>
> Question2:What is the best time complexity bound as far as we know, for the function that $1^{n}\rightarrow $a branching program in the Question 1.

**Tags:** cc.complexity-theory, reference-request, circuit-complexity, space-bounded, space-complexity

---

## 1 answers

### Answer by username_1 on 2015-01-05. Score: 2

Denoting the class of functions computed by branching programs of size $f(n)$ by $\text{BP}(f)$,
the best known bound seems to be the trivial $\text{DSPACE}(S(n)) \subseteq \text{BP}(2^{O(S(n))})$.
This matches the known inclusions $\text{DSPACE}(\log n) = \text{L} \subseteq \text{L}/poly = \text{BP}(poly)$; if a better bound were known then I would expect it to have been noted by Razborov in his FCT 1991 survey ([preprint](http://people.cs.uchicago.edu/%7Erazborov/files/fct.pdf)), or in Jukna's 2012 BFC textbook.


---

