Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR94-027 | 12th December 1994 00:00

A Note on Read-k Times Branching Programs


Authors: Stasys Jukna
Publication: 12th December 1994 00:00
Downloads: 1598


A syntactic read-k times branching program has the restriction
that no variable occurs more than k times on any path (whether or not
consistent). We exhibit an explicit Boolean function f which cannot
be computed by nondeterministic syntactic read-k times branching programs
of size less than exp(\sqrt{n}}k^{-2k}),
although its complement 1-f has a nondeterministic syntactic read-once
branching program of polynomial size.
This, in particular, means that the nonuniform analogue of
NLOGSPACE = co-NLOGSPACE fails for syntactic read-k times networks
with k = o(\log n). We also show that (even for k=1) the syntactic model
is exponentially weaker then more realistic "nonsyntactic" one.

The lower bound argument we use here is extremely easy (this simplicity is
one of the main results of this note).

ISSN 1433-8092 | Imprint