×

A hierarchy result for read-once branching programs with restricted parity nondeterminism (extended abstract). (English) Zbl 0996.68513

Nielsen, Mogens (ed.) et al., Mathematical foundations of computer science 2000. 25th international symposium, MFCS 2000, Bratislava, Slovakia, August 28 - September 1, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1893, 650-659 (2000).
Summary: Restricted branching programs are considered in complexity theory in order to study the space complexity of sequential computations and in applications as a data structure for Boolean functions. In this paper \((\oplus,k)\)-branching programs and \((\vee,k)\)-branching programs are considered, i.e., branching programs starting with a \(\oplus\)- (or \(\vee\)-)node with a fan-out of \(k\) whose successors are \(k\) read-once branching programs. This model is motivated by the investigation of the power of nondeterminism in branching programs and of similar variants that have been considered as a data structure. Lower bound methods for these variants of branching programs are presented, which allow to prove even hierarchy results for polynomial size \((\oplus,k)\)- and \((\vee,k\))-branching programs with respect to \(k\).
For the entire collection see [Zbl 0944.00070].

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDFBibTeX XMLCite