Non-deterministic branching programs with logarithmic repetition cannot efficiently compute small monotone CNFs

2016/04/06 by Oded Lachish, Lachish, Oded, Igor Razgon +1
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC

paper · pdf · doi:10.48550/arxiv.1604.01560

Minor changes made in the abstract and the introduction in order to correct several inaccuracies in the informal statements

arxiv created 2016/04/07 · arxiv updated 2016/04/08

Abstract

In this paper we establish an exponential lower bound on the size of syntactic non-deterministic read d-times branching programs for d ≤ log n /10⁵ computing a class of monotone CNFs with a linear number of clauses. This result provides the first separation of classes NP and co-NP for syntactic branching programs with a logarithmic repetition and the first separation of syntactic non-deterministic branching programs with a logarithmic repetition from small monotone CNFs.

Related

• Two types of branching programs with bounded repetition that cannot efficiently compute monotone 3-CNFs
• The splitting power of branching programs of bounded repetition and CNFs of bounded width
• On the read-once property of branching programs and CNFs of bounded treewidth
• No small nondeterministic read-once branching programs for CNFs of bounded treewidth
• Incremental branching programs