Time-space trade-offs for branching programs

摘要

Branching program depth and the logarithm of branching program complexity are lower bounds on time and space requirements for any reasonable model of sequential computation. In order to gain more insight to the complexity of branching programs and to the problems of time-space trade-offs one considers, on one hand, width-restricted and, on the other hand, depth-restricted branching programs. We present these computation models and the trade-off results already proved. We prove a new result of this type by presenting an effectively defined Boolean function whose complexity in depth-restricted one-time-only branching programs is exponential while its complexity even in width-2 branching programs is polynomial.