Satisfiability algorithm for syntactic read-\(k\)-times branching programs

DOI10.1007/s00224-020-09996-3zbMath1506.68039OpenAlexW3044773971MaRDI QIDQ2032296

Kazuhisa Seto, Atsuki Nagao, Junichi Teruyama

Publication date: 11 June 2021

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-020-09996-3

zbMATH Keywords

satisfiabilitypolynomial spacebranching programmoderately exponential timeread-\(k\)-times

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Data structures (68P05) Computational aspects of satisfiability (68R07)

Cites Work

• A nondeterministic space-time tradeoff for linear codes
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
• Time-space tradeoffs for branching programs
• Mining circuit lower bound proofs for meta-algorithms
• On lower bounds for read-\(k\)-times branching programs
• Improving Exhaustive Search Implies Superpolynomial Lower Bounds
• A Moderately Exponential Time Algorithm for k-IBDD Satisfiability
• A note on read-$k$ times branching programs
• The Shrinkage Exponent of de Morgan Formulas is 2
• Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Satisfiability algorithm for syntactic read-\(k\)-times branching programs