The power of polynomial size \(\Omega\)-branching programs. (English) Zbl 0644.68074

Meinel, Christoph

STACS 88, Theoretical aspects of computer science, Proc. 5th Annu. Symp., Bordeaux/France 1988, Lect. Notes Comput. Sci. 294, 81-90 (1988).

Summary: [For the entire collection see Zbl 0635.00015.]
In the following new types of branching programs, so-called \(\Omega\)- branching programs, \(\Omega \subseteq {\mathbb{B}}_ 2\), are introduced. The complexity classes related to polynomial-size \(\Omega\)-branching programs will be completely classified. Beside of identifying a new class \({\mathcal P}_{\{\oplus \}-BP}=L_{\{\oplus \}}/poly\) between L/poly and P/poly new characterizations of such fundamental complexity classes, like NL/poly and P/poly are obtained.

MSC:

68Q05	Models of computation (Turing machines, etc.) (MSC2010)
68Q25	Analysis of algorithms and problem complexity
94C10	Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68N01	General topics in the theory of software

Keywords:

branching programs; complexity classes

Citations:

Zbl 0642.68086; Zbl 0635.00015