Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1998 Copyright 1998 Universität Bonn, Institut für Informatik, Abt. V

Some Separation Problems on Randomized OBDDs
Marek Karpinski, Rustam Mubarakzjanov
[Download PostScript] [Download PDF]

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. In the second part of this paper, we show that the class PP (polynomial time probabilistic) and all of the 11 classes obtained by some intersection or union of BPP (polynomial time randomized), NP and coNP are different for the ordered case of read-once branching programs. We present also some complexity results on other classes of branching programs.

Last Change: 08/18/99 at 13:00:38
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope