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.


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