The power of nondeterminism in polynomial-size bounded-width branching programs (Q1116338)

The nondeterministic branching programs introduced by the author [Lect. Notes Comput. Sci. 233, 527-535 (1986; Zbl 0611.03021)] are considered as computing devices. Since some types of branching programs (BPs) characterize the nonuniform counterparts of the fundamental complexity classes DLOG, NLOG P, NP and \(NC^ 1\) [\textit{D. A. Barinton}, ``Bounded- width polynomial-size branching programs recognizing exactly those languages in \(NC^ 1\)''. In: Proc. 18th Symp. Theory Comput. IEEE 1986, 1-5; cf. J. Comput. Syst. Sci. 38, No.1, 150-164 (1989); the author, Modified branching programs and their computational power. Habilitationsschrift, Berlin 1988] the power of nondeterminism for some special types of BPs is investigated. The following two results are established: (1) 1-time-only nondeterministic, polynomial size, bounded-width BPs characterize the class \(NC^ 1\), which means that their power is exactly the same as the power of polynomial-size, bounded-width BPs. (2) 2-times-only nondeterministic, polynomial-size, bounded-width BPs are as powerful as nondeterministic, polynomial size BPs, i.e., they characterize the class NP/poly.