ECCC-Report TR99-044https://eccc.weizmann.ac.il/report/1999/044Comments and Revisions published for TR99-044en-usMon, 22 Nov 1999 18:17:25 +0200
Paper TR99-044
| On Complexity of Regular $(1,+k)$-Branching Programs |
Farid Ablayev
https://eccc.weizmann.ac.il/report/1999/044 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.
Mon, 22 Nov 1999 18:17:25 +0200https://eccc.weizmann.ac.il/report/1999/044