Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas

DOI10.1007/s10817-005-9006-xzbMath1109.68098OpenAlexW2149719182MaRDI QIDQ862399

Dmitry Itsykson, Michael Alekhnovich, Edward A. Hirsch

Publication date: 24 January 2007

Published in: Journal of Automated Reasoning (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10817-005-9006-x

zbMATH Keywords

contemporary algorithmspropositional satisfiability problem

Mathematics Subject Classification ID

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

Related Items

Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets ⋮ A dichotomy for local small-bias generators ⋮ Fast Pseudorandom Functions Based on Expander Graphs ⋮ Cryptographic hardness of random local functions. Survey ⋮ Locally computable UOWHF with linear shrinkage ⋮ Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms ⋮ On the algebraic immunity -- resiliency trade-off, implications for Goldreich's pseudorandom generator ⋮ Advice complexity of adaptive priority algorithms ⋮ The complexity of inverting explicit Goldreich's function by DPLL algorithms ⋮ Toward a model for backtracking and dynamic programming ⋮ Special issue in memory of Misha Alekhnovich. Foreword ⋮ Lower bounds for \(k\)-DNF resolution on random 3-CNFs ⋮ The Complexity of Inversion of Explicit Goldreich’s Function by DPLL Algorithms ⋮ On exponential time lower bound of Knapsack under backtracking ⋮ Limitations of restricted branching in clause learning ⋮ On linear-size pseudorandom generators and hardcore functions ⋮ Tight Upper Bound on Splitting by Linear Combinations for Pigeonhole Principle ⋮ Non-interactive zero-knowledge in pairing-free groups from weaker assumptions ⋮ On the One-Way Function Candidate Proposed by Goldreich ⋮ Resolution over linear equations modulo two

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Toward a model for backtracking and dynamic programming
• Lower bounds for polynomial calculus in the case of nonbinomial ideals.
• SAT local search algorithms: Worst-case study
• Short proofs are narrow—resolution made simple
• Pseudorandom Generators in Propositional Proof Complexity
• A sharp threshold in proof complexity
• Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving

This page was built for publication: Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas