Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs
From MaRDI portal
Publication:5136279
DOI10.4230/LIPIcs.ISAAC.2017.58zbMath1457.68128OpenAlexW2784061433MaRDI QIDQ5136279
Atsuki Nagao, Kazuhisa Seto, Junichi Teruyama
Publication date: 25 November 2020
Full work available at URL: https://doi.org/10.4230/LIPIcs.ISAAC.2017.58
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Data structures (68P05) Computational aspects of satisfiability (68R07)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis
- 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
- An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
- Nonuniform ACC Circuit Lower Bounds
- Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms
- A Moderately Exponential Time Algorithm for k-IBDD Satisfiability
- The Complexity of Satisfiability of Small Depth Circuits
- A note on read-$k$ times branching programs
- An algorithm for the satisfiability problem of formulas in conjunctive normal form
- Algorithms and Computation
- STACS 2004
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
This page was built for publication: Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs
