2015/10/19 by Igor Razgon, Razgon, Igor
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Optimization and Search Problems #cs.CC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1510.05486
It 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
openalex publication_date 2015/10/19 · arxiv created 2016/05/16 · arxiv updated 2016/05/17 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
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-k-times \sc nbps and the second class generalizes oblivious read k times branching programs. The lower bounds remain exponential for k ≤ log n/a where a is a sufficiently large constant.