An Exact Algorithm for Oblivious Read-Twice Branching Program Satisfiability

Kazuhisa SETO  Junichi TERUYAMA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.6   pp.1019-1024
Publication Date: 2016/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.1019
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
oblivious branching program,  read twice,  satisfiability,  exact algorithm,  

Full Text: PDF>>
Buy this Article

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.