An Exact Algorithm for Oblivious Read-Twice Branching Program Satisfiability
K. Seto, Junichi Teruyama · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2016
We propose an exact algorithm to determine the satisfiability of oblivious read-twice branching programs. Our algorithm runs in $2^{\left(1 - \Omega(\frac{1}{\log c})\right)n}$ time for instances with n variables and cn nodes.