On the read-once property of branching programs and CNFs of bounded treewidth

DOI10.1007/S00453-015-0059-XzbMATH Open1350.68156arXiv1411.0264OpenAlexW2128906567MaRDI QIDQ309788FDOQ309788

Authors: Igor Razgon 

Publication date: 7 September 2016

Published in: Algorithmica (Search for Journal in Brave)

Abstract: In this paper we prove a space lower bound of $n^{Omega(k)}$ for non-deterministic (syntactic) read-once branching programs ({sc nrobp}s) on functions expressible as {sc cnf}s with treewidth at most $k$ of their primal graphs. This lower bound rules out the possibility of fixed-parameter space complexity of {sc nrobp}s parameterized by $k$. We use lower bound for {sc nrobp}s to obtain a quasi-polynomial separation between Free Binary Decision Diagrams and Decision Decomposable Negation Normal Forms, essentially matching the existing upper bound introduced by Beame et al. and thus proving the tightness of the latter.

Full work available at URL: https://arxiv.org/abs/1411.0264

Recommendations

• No small nondeterministic read-once branching programs for CNFs of bounded treewidth
• On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
• On Tseitin formulas, read-once branching programs and treewidth
• On Tseitin formulas, read-once branching programs and treewidth
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs

zbMATH Keywords

bounded treewidthlower boundsparameterized complexityspace complexityread-once branching programsCNFs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Branching Programs and Binary Decision Diagrams
• Boolean function complexity. Advances and frontiers.
• Title not available (Why is that?)
• A note on read-$k$ times branching programs
• No small nondeterministic read-once branching programs for CNFs of bounded treewidth
• Title not available (Why is that?)
• Treewidth in Verification: Local vs. Global
• Decomposable negation normal form

Cited In (15)

• Title not available (Why is that?)
• On the relative succinctness of sentential decision diagrams
• Characterizing Tseitin-formulas with short regular resolution refutations
• On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
• On Tseitin formulas, read-once branching programs and treewidth
• On Tseitin formulas, read-once branching programs and treewidth
• Title not available (Why is that?)
• A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
• Characterizing Tseitin-Formulas with Short Regular Resolution Refutations
• The splitting power of branching programs of bounded repetition and CNFs of bounded width
• On limitations of structured (deterministic) DNNFs
• No small nondeterministic read-once branching programs for CNFs of bounded treewidth
• Read-Once Branching Programs for Tree Evaluation Problems
• On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
• Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs

This page was built for publication: On the read-once property of branching programs and CNFs of bounded treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q309788)