ECCC-Report TR98-051https://eccc.weizmann.ac.il/report/1998/051Comments and Revisions published for TR98-051en-usMon, 31 Aug 1998 16:49:26 +0300
Paper TR98-051
| A probabilistic nonequivalence test for syntactic (1,+k)-branching programs |
Petr Savicky
https://eccc.weizmann.ac.il/report/1998/051
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.
Mon, 31 Aug 1998 16:49:26 +0300https://eccc.weizmann.ac.il/report/1998/051