Times Branching Programs

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 i\Omega ip n k 2k jj ; although its complement :f has a nondeterministic syntactic read-once branching program of polynomial size. This, in particular, means that the nonuniform analogue of NLOGSPACE = co \Gamma 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. Subject classification: 68Q05, 68Q25 Email: jukna@uni-trier.de y Research done partly while visiting Fachbereich Informatik, Universitat Dortmund under the support of Alexander von Humboldt Foundation. 1 Introduction We will consider the classical model of switching-and-rectifier netwo..