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

摘要

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)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?klog(n2k)2n for k=o(n2) on the size of any nondeterministic (1+k) -ReBP computing permutation function PERMn2 on n2 arguments. The proof is based on combination of decomposing of (1+k) -ReBP with communication complexity technique.