## 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$$.

### MSC:

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

### Citations:

Zbl 0633.00025; Zbl 0611.03021