F. Odeh, I. Tadjbakhsh
Archive for Rational Mechanics and Analysis
We obtain the first non-trivial time-space tradeoff lower bound for functions f:{0,1}n → {0,1} on general branching programs by exhibiting a Boolean function f that requires exponential size to be computed by any branching program of length (1 + ε) n, for some constant ε > 0. We also give the first separation result between the syntactic and semantic read-k models (A. Borodin et al., Comput. Complexity 3 (1993), 1-18) for k > 1 by showing that polynomial-size semantic read-twice branching programs can compute functions that require exponential size on any semantic read-k branching program. We also show a time-space tradeoff result on the more general R-way branching program model (Borodin et al., 1993): for any k, we give a function that requires exponential size to be computed by length kn q-way branching programs, for some q = q(k). This result gives a similar tradeoff for RAMs, and thus provides the first nontrivial time-space tradeoff for decision problems in this model.
F. Odeh, I. Tadjbakhsh
Archive for Rational Mechanics and Analysis
M. Shub, B. Weiss
Ergodic Theory and Dynamical Systems
John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence
Shu Tezuka
WSC 1991