__
TR94-027 | 12th December 1994 00:00
__

#### A Note on Read-k Times Branching Programs

**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).