期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：branching programs, Communication complexity, hierarchies, lower bounds, nondeterminism, partitioned
