A hierarchy result for read-once branching programs with restricted parity nondeterminism

摘要

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 (circle plus, k)-branching programs and (v, k)-branching programs are considered, i.e., branching programs starting with a circle plus- (or V-)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 and hierarchy results for polynomial size (circle plus, k)- and (V, k)-branching programs with respect to k are presented. (c) 2005 Elsevier B.V. All rights reserved.