A lower bound on branching programs reading some bits twice

• Published in: Theoretical computer science 1997-02, Vol.172 (1), p.293-301
• Main Authors: Savicky, Petr, Zak, Stanislav
• Format: Article
• Language: English
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/S0304-3975(96)00183-1

By (1, + k( n))-branching programs (b.p.'s) we mean those b.p.'s which during each of their computations are allowed to test at most k( n) input bits repeatedly. For a Boolean function computable within polynomial time a trade-off is presented between the size and the number of repeatedly tested input bits of any b.p. P computing the function. Namely, if at most k( n) repeated tests are allowed, where log 2 n ⩽ k(n) ⩽ n (1000 log 2 n) , then the size of P is at least exp(Ω( n (k(n)log 2 n )) 1 2 ) . This is exponential whenever k( n) ⩽ n α for a fixed α < 1 and superpolynomial whenever k(n) = o( n log 3 2 n ) . The presented result is a step towards a superpolynomial lower bound for 2-b.p.'s which is an open problem since 1984 when the first superpolynomial lower bounds for 1-b.p.'s were proven (Wegener, 1988; Žák, 1984). The present result is an improvement on (Žák, 1995).