Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR97-050 | 27th October 1997 00:00

A subexponential lower bound for branching programs restricted with regard to some semantic aspects


Authors: Stanislav Zak
Publication: 4th November 1997 09:52
Downloads: 1127


Branching programs (b.p.s) or binary decision diagrams are a
general graph-based model of sequential computation. The b.p.s of
polynomial size are a nonuniform counterpart of LOG. Lower bounds
for different kinds of restricted b.p.s are intensively
investigated. The restrictions based on the number of tests of
variables during any computation (along any path in the case of
syntactic b.p.s, resp.) are very important. Various superpoly-
nomial or even exponential lower bounds are known for 1-b.p.s,
(1,+k)-b.p.s, and syntactic k-b.p.s.
In the paper we present a restriction of another type -
the so-called gentle branching programs (g-b.p.s) together with
the following results.
1. For each 1-b.p. P there is a gentle 1-b.p. P' computing the
same function such that |P'| =< 3|P|.
2. Some Boolean functions which are superpolynomially (or even
exponentially) hard for 1-b.p.s are polynomially easy for g-b.p.s.
3. The same holds for some Boolean functions which are superpoly-
nomially hard for (1,+k)-b.p.s or for syntactic k-b.p.s.
4. The functions whose sequences cause the hierarchies for
(1,+k)-b.p.s and for syntactic k-b.p.s (both with respect to k)
are polynomially easy for g-b.p.s.
5. We find a function in P which is superpolynomially hard for
g-b.p.s. The proof is based on a lower bound theorem.
Both, the lower bound theorem and the definition of genttle
branching programs are derived from a deeper consideration of the
phenomenon of branching of computations.

ISSN 1433-8092 | Imprint