Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1998 Copyright 1998 University of Bonn, Department of Computer Science, Abt. V
85196

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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V