Randomization and nondeterminsm are incomparable for ordered read-once branching programs
Farid Mansurovich Ablayev · 1997
. In [3] 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 readonce 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. 1 Preliminaries Branching programs is well known model of computation for discrete functions [14]. Many types of restricted branching programs have been investigated as important theoretical model of computations [9]. Ordered read-once branching program or ordered binary decision diagrams (OBDD) [4, 15] also important for...