We present a new boolean function for which any Ordered Binary Decision Diagram (OBDD) computing it has an exponential number of nodes. This boolean function is obtained from Nisan's pseudorandom generator to derandomize space bounded randomized algorithms. Though the relation between hardness and randomness for computational models is well known, to the best of our knowledge, this is the first study relating the problem of proving lower bounds for OBDDs to the issue of pseudorandom generators for space bounded computation. Using the same technique to prove the OBDD size lower bound, we place a lower bound on the size of families of hash functions used in Nisan's pseudorandom generator. This lower bound rules out one method of obtaining improved derandomizations of space bounded randomized algorithms.
展开▼
