Time-Space Tradeoffs for Branching Programs

We obtain the first non-trivial time-space tradeoff lower bound for functions f: {0, 1}/sup n//spl rarr/{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+/spl epsiv/)n, for some constant /spl epsiv/>0. We also give the first separation result between the syntactic and semantic read-k models for k>1 by showing that polynomial-size semantic read-twice branching programs can compute functions that require exponential size on any syntactic read-k branching program. We also show a time-space tradeoff result on the more general R-way branching program model: 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).

Authors

• Paul Beame
• Michael E. Saks
• T. S. Jayram

Keywords

• Binary decision diagrams
• Polynomials
• Computer science
• Mathematics
• Complexity theory
• Input variables
• Microwave integrated circuits
• Computational modeling
• Sorting
• Pattern matching
• Branching Program
• Boolean Function
• Start Node
• Lower Bound
• Upper Bound
• Sufficiently Large
• Decision Tree
• Proof Of Theorem
• L-arginine
• Mutual Information
• Finite Set
• Off-diagonal
• Matrix M
• Sum Of Terms
• Pair Of Sets
• Finite Group
• Sink Node
• Input Bits
• Sum Of Entries
• N Log N
• Prime Power
• Disjoint Sets
• Time And Space