Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR98-051 | 20th July 1998 00:00

A probabilistic nonequivalence test for syntactic (1,+k)-branching programs


Authors: Petr Savicky
Publication: 31st August 1998 16:49
Downloads: 1764


Branching programs are a model for representing Boolean
functions. For general branching programs, the
satisfiability and nonequivalence tests are NP-complete.
For read-once branching programs, which can test each
variable at most once in each computation, the satisfiability
test is trivial and there is also a probabilistic polynomial
time test of nonequivalence of two diagrams by a result
of Blum, Chandra and Wegman (1980).

We generalize the satisfiability test and the probabilistic
nonequivalence test for syntactic (1,+k)-branching programs.
The algorithms work in time (cn/k)^k times a polynomial
in the input size, where c is an absolute constant. This
is better than the exhaustive search whenever k=o(n).

The restriction leading to syntactic (1,+k)-branching programs
is that for every path from the source to the 1-sink, there are
at most k variables that are read more than once. Let us point
out that even (1,+1)-branching programs are strictly more
powerfull than read-once branching programs. There are functions
with polynomial size (1,+1)-branching programs such that every
read-once branching program for them is of exponential size.

ISSN 1433-8092 | Imprint