期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：OBDD , pseudorandom generators , randomized space bounded algorithms
