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 fn in n variables such that: 1) fn 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 fn has exponential size. In this paper we present a simple boolean function gn in n variables such that: 1) gn 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 fn has exponential size. These mean that BPP and NP are incomparable in the context of ordered read-once branching program
展开▼
