ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR94-027 | 12th December 1994 00:00

A Note on Read-k Times Branching Programs

RSS-Feed




TR94-027
Authors: Stasys Jukna
Publication: 12th December 1994 00:00
Downloads: 431
Keywords: 


Abstract:

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