## 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).

### MSC:

 68Q25 Analysis of algorithms and problem complexity

### Keywords:

sequential computation; Real-time branching programs
Full Text: