ECCC-Report TR94-027https://eccc.weizmann.ac.il/report/1994/027Comments and Revisions published for TR94-027en-usMon, 12 Dec 1994 00:00:00 +0200
Paper TR94-027
| A Note on Read-k Times Branching Programs |
Stasys Jukna
https://eccc.weizmann.ac.il/report/1994/027A 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).
Mon, 12 Dec 1994 00:00:00 +0200https://eccc.weizmann.ac.il/report/1994/027