__
TR99-044 | 30th September 1999 00:00
__

#### On Complexity of Regular $(1,+k)$-Branching Programs

**Abstract:**
A regular $(1,+k)$-branching program ($(1,+k)$-ReBP) is an

ordinary branching program with the following restrictions: (i)

along every consistent path at most $k$ variables are tested more

than once, (ii) for each node $v$ on all paths from the source to

$v$ the same set $X(v)\subseteq X$ of variables is tested, and

(iii) on each path from the source to a sink all variables $X$ are

tested.

We show that polynomial size $(1,+1)$-ReBP-s are more powerful than

polynomial size read-once branching programs and that polynomial size

$(1,+(k+1))$-ReBP-s are more powerful than polynomial size

$(1,+k)$-ReBP-s.

We prove lower bound $2^{(n-k)/2-k\log (n^2/k)}/2\sqrt{n}$ for

$k=o(n^2)$ on the size of any nondeterministic $(1,+k)$-ReBP

computing permutation function $PERM_{n^2}$ on $n^2$ arguments. The

proof is based on combination of decomposing of $(1,+k)$-ReBP with

communication complexity technique.