The power of nondeterminism in polynomial-size bounded-width branching programs. (English) Zbl 0642.68086

Fundamentals of computation theory, Proc. Int. Conf., Kazan/USSR 1987, Lect. Notes Comput. Sci. 278, 302-309 (1987).
[For the entire collection see Zbl 0633.00025.]
Nondeterministic branching programs introduced by the author [Lect. Notes Comput. Sci. 233, 527-535 (1986; Zbl 0611.03021)] spelt out to be an interesting computational tool for describing higher complexity classes. The investigation of the power of nondeterminism in the case of bounded- width nondeterministic branching programs yields: while polynomial-size bounded-width 1-time-only-nondeterministic branching programs are not more powerful than polynomial-size (usual) bounded-width branching programs, polynomial-size, bounded-width k-times-only-nondeterministic branching programs, \(k>1\), are as powerful as polynomial-size, unbounded- width, nondeterministic branching programs, i.e. \({\mathcal P}_{bw-n_ 1BP}=NC^ 1\) and \({\mathcal P}_{bw-n_ kBP}=NP/poly\), \(k>1\).


68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity