1-1hit |
Kazuhisa SETO Junichi TERUYAMA
We propose an exact algorithm to determine the satisfiability of oblivious read-twice branching programs. Our algorithm runs in $2^{left(1 - Omega(rac{1}{log c}) ight)n}$ time for instances with n variables and cn nodes.