Some Separation Problems on Randomized OBBDs
Marek Karpiński, Rustam Mubarakzjanov · 1998
We investigate the relationships between complexity classes of Boolean functions that are computable by polynomial size branching programs. In the first part of this paper, we consider different general cases of branching programs: deterministic, non-deterministic, randomized and probabilistic, with and without restrictions on times or on order of reading inputs. We are able to show the following. If $Q, Q_1, Q_2$ are some of these complexity classes such that there are two functions $f_1, f_2$ in $Q$ but not belonging to $Q_1$, $Q_2$ respectively then there is a function $f \in Q\setminus (Q_1\cup Q_2)$. This fact gives a possibility to show non emptiness of different combinations of the complexity classes.