On Probabilistic OBDDs With Constant Width.

Rustam Mubarakzjanov: On Probabilistic OBDDs With Constant Width CSIT 2000 : 62-68

Abstract

One of central open problems in the complexity theory is the question: NC^1=?LOGSPACE. It is known that LOGSPACE/poly(n) and NC^1/poly(n) are equal respectively to the class of all Boolean functions computable by branching programs of the polynomial size and to the class of all Boolean functions computable by polynomial size branching programs of a constant width. Read-once ordered branching programs (or OBDDs) having a constant width (cwOBDD for short) are studied in this work. An other restriction for a cwOBDD is a requirement that the connections between neighboring levels of the cwOBDD are the same for all such pairs of levels . We use the notation fixOBDDs for such programs.

We present a new function computable by probabilistic (without bo\-unded error) fixOBDD. There is no polynomial non-deterministic OBDD and no polynomial randomized OBDD computing this function. It is known that the complexity classes P, BPP, NP, coNP in the context of OBDDs are different. We show that these classes are equal in the context of cwOBDDs and in the context of fixOBDDs as well.

Copyright © 2000 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

Heinz Schweppe and Yuri S. Kabalnov (Eds.): CSIT'2000, Proceedings of 2nd International Workshop on Computer Science and Information Technologies, September 18-23, 2000, Ufa, Russia. USATU Publishers & JurInfoR-MSU Publishing 2000, ISBN 5-86911-312-1

Electronic Edition