Two types of branching programs with bounded repetition that cannot efficiently compute monotone 3-CNFs
arXiv:1510.05486
Abstract
It is known that there are classes of 2-CNFs requiring exponential size non-deterministic read-once branching programs to compute them. However, to the best of our knowledge, there are no superpolynomial lower bounds for branching programs of a higher repetition computing a class of 2-CNFs. This work is an attempt to make a progress in this direction. We consider a class of monotone 3-CNFs that are almost 2-CNFs in the sense that in each clause there is a literal occurring in this clause only. We prove exponential lower bounds for two classes of non-deterministic branching programs. The first class significantly generalizes monotone read--times {\sc nbp}s and the second class generalizes oblivious read times branching programs. The lower bounds remain exponential for where is a sufficiently large constant.
arXiv commentIt turned out that this is not the first result separating branching programs with a higher repetition and CNFs (which was the motivation in version 1). Corresponding results cited and the motivation significantly narrowed