An exponential lower bound for real-time branching programs. (English) Zbl 0627.68044

Branching programs are a general model of sequential computation. One of their computational features is their possibility to question (repeatedly) the information from each input bit. Real-time branching programs make at most n questions when computing on an input of length n. The restriction “real-time” allows to find a simple language which requires the lower bound \(2^{\sqrt{2n/8}}\) on memory \((=\) the state space).


68Q25 Analysis of algorithms and problem complexity
Full Text: DOI