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.


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.

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