Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
type: Item
instance of: scholarly article
title: Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
zbMATH Open document ID: 1109.68098
author: Michael Alekhnovich
author: Dmitry Itsykson
author: Edward A. Hirsch
published in: Journal of Automated Reasoning
publication date: 2007-01-24T00:00:00Z
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 5118122
zbMATH Keywords: contemporary algorithms
zbMATH Keywords: propositional satisfiability problem
MaRDI profile type: Publication
full work available at URL: s10817-005-9006-x
OpenAlex ID: W2149719182
cites work: A sharp threshold in proof complexity
cites work: Q5501251
cites work: Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
cites work: Pseudorandom Generators in Propositional Proof Complexity
cites work: Toward a model for backtracking and dynamic programming
cites work: Lower bounds for polynomial calculus in the case of nonbinomial ideals.
cites work: Short proofs are narrow—resolution made simple
cites work: A machine program for theorem-proving
cites work: A Computing Procedure for Quantification Theory
cites work: SAT local search algorithms: Worst-case study
cites work: Q5501274
cites work: Q4952609
DOI: 10.1007/S10817-005-9006-X
description: scientific article; zbMATH DE number 5118122