Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR99-044 | 30th September 1999 00:00

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

TR99-044
Authors: Farid Ablayev
Publication: 22nd November 1999 18:17
Keywords:

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.

ISSN 1433-8092 | Imprint