Time–Space Tradeoffs for Branching Programs

ISSN： 0022-0000

Source： Journal of Computer and System Sciences, Vol.63, Iss.4, 2001-12, pp. : 542-572

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

We obtain the first non-trivial time–space tradeoff lower bound for functions f: {0, 1}ⁿ→{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 tradedoff for decision problems in this model. © 2001 Elsevier Science (USA).