Some Separation Problems on Randomized OBDDs.

Marek Karpinski, Rustam Mubarakzjanov: Some Separation Problems on Randomized OBDDs CSIT 1999 : E/E

Abstract

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 minus union of Q_1 and 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.

Copyright © 1999 by the Institute for Contemporary Education "JurInfoR-MSU". Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the CSIT copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Institute for Contemporary Education JMSUICE. To copy otherwise, or to republish, requires a fee and/or special permission from the JMSUICE.

Printed Edition

Ch. Freytag and V. Wolfengagen (Eds.): CSIT'99, Proceedings of 1st International Workshop on Computer Science and Information Technologies, January 18-22, 1999, Moscow, Russia. MEPhI Publishing 1999, ISBN 5-7262-0263-5

Electronic Edition