# zbMATH — the first resource for mathematics

The power of polynomial size $$\Omega$$-branching programs. (English) Zbl 0644.68074
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