Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR97-021 | 16th May 1997 00:00

Randomization and nondeterminsm are incomparable for ordered read-once branching programs

RSS-Feed




TR97-021
Authors: Farid Ablayev
Publication: 27th May 1997 09:36
Downloads: 3141
Keywords: 


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.



ISSN 1433-8092 | Imprint