Abstract:
In the manuscript F. Ablayev and M. Karpinski, On the power of randomized branching programs (generalization of ICALP'96 paper results for the case of pure boolean function, available at http://www.ksu.ru/~ablayev) we exhibited a simple boolean functions $f_n$ in $n$ variables such that: 1) $f_{n}$ can be computed by polynomial size randomized ordered read-once branching program with one sided small error; 2) any nondeterministic ordered read-once branching program that computes $f_n$ has exponential size. In this paper we present a simple boolean function $g_n$ in $n$ variables such that: 1) $g_n$ can be computed by polynomial size nondeterministic ordered read-once branching program; 2) any two-sided error randomized ordered read-once branching program that computes $f_n$ has exponential size. These mean that $BPP$ and $NP$ are incomparable in the context of ordered read-once branching program.