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 programsof size less than exp(sqrt{n}}k^{-2k}), although its complement 1-f has a nondeterministic syntactic read-oncebranching program of polynomial size.This, in particular, means that the nonuniform analogue ofNLOGSPACE = co-NLOGSPACE fails for syntactic read-k times networkswith k = o(log n). We also show that (even for k=1) the syntactic model is exponentially weaker then more realistic "nonsyntactic" one.
展开▼
