Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms

DOI10.1007/11758471_9zbMath1183.68305OpenAlexW1710911229MaRDI QIDQ3434543

Evgeny Dantsin, Alexander Wolpert, Edward A. Hirsch

Publication date: 2 May 2007

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11758471_9

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Related Items (6)

A Moderately Exponential Time Algorithm for k-IBDD Satisfiability ⋮ A satisfiability algorithm and average-case hardness for formulas over the full binary basis ⋮ The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs ⋮ A moderately exponential time algorithm for \(k\)-IBDD satisfiability ⋮ Experimental Study of the Shortest Reset Word of Random Automata ⋮ Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs

This page was built for publication: Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms