__
TR00-057 | 25th July 2000 00:00
__

#### An Improved Hierarchy Result for Partitioned BDDs

**Abstract:**
One of the great challenges of complexity theory is the problem of

analyzing the dependence of the complexity of Boolean functions on the

resources nondeterminism and randomness. So far, this problem could be

solved only for very few models of computation. For so-called

partitioned binary decision diagrams, which are a restricted variant of

nondeterministic read-once branching programs, Bollig and Wegener have

proven an astonishing hierarchy result which shows that the smallest

possible decrease of the available amount of nondeterminism may incur

an exponential blow-up of the branching program size.

They have shown that k-partitioned BDDs which may nondeterministically

choose between k alternative subprograms may be exponentially larger

than (k+1)-partitioned BDDs for the same function if

k = o((log n/loglog n)^{1/2}), where n is the input size.

In this paper, an improved hierarchy result is established which still

works if the number of nondeterministic decisions is

O((n/log^{1+c} n)^{1/4}), where c > 0 is an arbitrary small constant.