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.


1 Answer 1


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), or in Jukna's 2012 BFC textbook.


Your Answer

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

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