COMPLEXITY THEORETICAL RESULTS ON NONDETERMINISTIC GRAPH-DRIVEN READ-ONCE BRANCHING PROGRAMS

摘要

Branching programs are a well-established computation model for boolean functions, especially read-once branching programs (BPls) have been studied intensively. Recently two restricted nondeter-ministic (parity) BP1 models, called nondeterministic (parity) graph-driven BPls and well-structured nondeterministic (parity) graph-driven BPls, have been investigated. The consistency test for a BP-model M is the test whether a given BP is really a BP of model M. Here it is proved that the consistency test is co-NP-complete for nondeterministic (parity) graph-driven BPls. Moreover, a lower bound technique for nondeterministic graph-driven BPls is presented. The method generalizes a technique for the well-structured model and is applied in order to answer in the affirmative the open question whether the model of nondeterministic graph-driven BPls is a proper restriction of nondeterministic BPls (with respect to polynomial size).