A probabilistic nonequivalence test for syntactic (1,+k)-branching programs
Petr Savický · Digital Repository (National Repository of Grey Literature) · 1998
We present a satisfiability test and a probabilistic nonequivalence test for syntactic (1; +k)-branching programs. The satisfiability test works in time at most O( \\Gamma 4en k \\Delta k sd), where s and d are the size and depth of the input branching program. The probabilistic nonequivalence test works in time O( \\Gamma 12en k \\Delta k sd log 2 n). The result has consequences also for parity syntactic (1; +k)-branching programs. 1 Introduction A nondeterministic branching program (or shortly bp) for representing a Boolean function f(x 1 ; x 2 ; : : : ; x n ) is an acyclic directed graph with one source and two sinks labeled by 0 and 1. We distinguish two kinds of nonsink nodes. A nondeterministic node has an arbitrary number of outgoing edges without label. A testing node has two outgoing edges labeled by x i and ¯ x i for some i = 1; 2; : : : ; n. For an assignment a 1 ; a 2 ; : : : ; a n of the variables, we have f(a 1 ; a 2 ; : : : ; a n ) = 1 if and only if there is ...