A superpolynomial lower bound for (1,+k(n))-branching programs

Abstract

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 J computable within polynomial time a trade-off has been proven between the number of repeatedly tested bits and the size of each b. p. P which computes J. If at most ≫√n/48(log(c(n)))²⌋ — 1 repeated tests are allowed then the size of P is at least c(n). This yields superpolynomial lower bounds for e. g. (1, +√n/48(log(n)loglog(n))²) -b. p.'s and for (1, +√n/48(log(n))⁴)-b. p.'s.

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 [6], [7].