BP(f)=O(L(f)/sup 1+έ/)
Oliver Giel · 2002
Any B/sub 2/-formula of size /spl Lscr/ can be transformed into a branching program of size O(e/spl Lscr//sup 1+/spl epsi//)for arbitrary E>0. The presented proof is based on a technique due to R. Cleve (1991) to simulate balanced algebraic formulas of size s by algebraic straight-line programs that employ a constant number of registers and have length O(s/sup 1+/spl epsi//). The best previously known simulation of B2-formulas of size C by branching programs achieves a branching program size of O(/spl Lscr//sup 1.195/).