Polynomial size Ω-branching programs and their computational power

In the following new types of branching programs, so-called Ω-branching programs, Ω ⊆ B2, are introduced. The complexity classes related to polynomial-size Ω-branching programs will be completely classified. In addition to identifying a new class P {⊕} − BP = ⊕L/poly between L/poly and P/poly, new characterizations of such fundamental space complexity classes like NL/poly = co-NL/poly and P/poly are obtained. Using these characterizations we relate the complexity of the mentioned classes to those of some extremely restricted problems resembling the graph accessibility problem.

Authors

• Christoph Meinel

Keywords

No keywords are indexed for this paper.