ECCC-Report TR97-021https://eccc.weizmann.ac.il/report/1997/021Comments and Revisions published for TR97-021en-usTue, 27 May 1997 09:36:14 +0300
Paper TR97-021
| Randomization and nondeterminsm are incomparable for ordered read-once branching programs |
Farid Ablayev
https://eccc.weizmann.ac.il/report/1997/021
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.
Tue, 27 May 1997 09:36:14 +0300https://eccc.weizmann.ac.il/report/1997/021