A moderately exponential time algorithm for k-IBDD satisfiability

DOI10.1007/S00453-017-0332-2MaRDI QIDQ722517zbMATH OpenOpenAlexWikidataFDO

Authors Atsuki Nagao, Kazuhisa Seto, Junichi Teruyama

Publication date 26 July 2018

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-017-0332-2

zbMATH Keywords

satisfiabilityindexed binary decision diagrammoderately exponential timeordered binary decision diagram

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• A moderately exponential time algorithm for \(k\)-IBDD satisfiability
• On \(k\)-positive satisfiability problem
• Satisfiability algorithm for syntactic read-\(k\)-times branching programs
• Satisfiability algorithm for syntactic read-\(k\)-times branching programs
• scientific article; zbMATH DE number 1701749

Cites work

• A satisfiability algorithm for \(\mathrm{AC}^0\)
• Algorithms and Computation
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Branching Programs and Binary Decision Diagrams
• Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms
• Graph-Based Algorithms for Boolean Function Manipulation
• Improving exhaustive search implies superpolynomial lower bounds
• Mining circuit lower bound proofs for meta-algorithms
• Nonuniform ACC circuit lower bounds
• STACS 2004

Cited in

(2)

• A moderately exponential time algorithm for \(k\)-IBDD satisfiability
• Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression

This page was built for publication: A moderately exponential time algorithm for \(k\)-IBDD satisfiability

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