An exponential lower bound for one-time-only branching programs. (English) Zbl 0558.68044

Mathematical foundations of computer science, Proc. 11th Symp., Praha/Czech. 1984, Lect. Notes Comput. Sci. 176, 562-566 (1984).
[For the entire collection see Zbl 0544.00022.]
Branching programs (b.p.) are a generalization of deterministic space bounded Turing machines (Tm). A b.p. is a finite, oriented acyclic graph with one source. The intuition is as follows. By a configuration of a Tm we mean the full state of the machine without the contents of the input tape. The b.p. corresponding to the machine in question on words of length n is a graph where the nodes are the configurations reachable during computations on inputs of length n, and the edges are given by the transition function. A computation is a path from the source \((=\) the initial configuration) to a sink. The next action (a branching in a node) is given by the contents of the cell scanned by the input head. We say that the cell is asked. It is clear that the lower bound F on the number of nodes of b.p.’s implies the lower bound log F on the tape of Tm’s. The aim is to prove an overpolynomial bound on b.p.’s for a language from P (LOG\(\neq P)\). In the paper, the exponential lower bound \(2^{\sqrt{2n}/3-\log (\sqrt{2n}/3)}\) is proved for a special type (one- time-only) of b.p.’s. The witness language is that of half-cliques \((=\) one half of the graph is a clique and the other one is an empty graph). The one-time-only b.p.’s are such that during a computation each input cell is asked at most one time. We see that they are a model of on-line computation. They are not the best model since on the two-times-only b.p.’s the language of half-cliques requires only a polynomial bound. Now, the author knows an exponential lower bound for real-time b.p.’s (real-time \(=\) the input cells may be asked repeatedly but at most n questions may be performed when computing on inputs of length n).


68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)


Zbl 0544.00022