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

DOI10.1007/S00453-015-0059-XMaRDI QIDQ309788zbMATH OpenOpenAlexFDO

Authors Igor Razgon

Publication date 7 September 2016

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.0264, https://eprints.bbk.ac.uk/id/eprint/15405/1/15405.pdf

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1946853 (Why is no real title available?)
• scientific article; zbMATH DE number 1559594 (Why is no real title available?)
• A note on read-$k$ times branching programs
• Boolean function complexity. Advances and frontiers.
• Branching Programs and Binary Decision Diagrams
• Decomposable negation normal form
• No small nondeterministic read-once branching programs for CNFs of bounded treewidth
• Treewidth in Verification: Local vs. Global

Cited in

(15)

• 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
• scientific article; zbMATH DE number 619536 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 1332670 (Why is no real title available?)
• 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

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)