Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
From MaRDI portal
Publication:862399
DOI10.1007/S10817-005-9006-XzbMATH Open1109.68098OpenAlexW2149719182MaRDI QIDQ862399FDOQ862399
Authors: Michael Alekhnovich, Dmitry Itsykson, 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
Recommendations
Cites Work
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- Pseudorandom Generators in Propositional Proof Complexity
- Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
- Short proofs are narrow—resolution made simple
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lower bounds for polynomial calculus in the case of nonbinomial ideals.
- Toward a model for backtracking and dynamic programming
- A sharp threshold in proof complexity
- SAT local search algorithms: Worst-case study
- Exponential bounds for DPLL below the satisfiability threshold
Cited In (32)
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- On exponential time lower bound of Knapsack under backtracking
- Title not available (Why is that?)
- On the one-way function candidate proposed by Goldreich
- Limitations of restricted branching in clause learning
- Hard satisfiable formulas for splittings by linear combinations
- Parameterized complexity of DPLL search procedures
- Lower bounds for \(k\)-DNF resolution on random 3-CNFs
- Special issue in memory of Misha Alekhnovich. Foreword
- Toward a model for backtracking and dynamic programming
- A note on SAT algorithms and proof complexity
- Fast pseudorandom functions based on expander graphs
- A dichotomy for local small-bias generators
- Advice complexity of adaptive priority algorithms
- Resolution over linear equations modulo two
- Exponential lower bounds for DPLL algorithms on satisfiable random 3-CNF formulas
- On linear-size pseudorandom generators and hardcore functions
- Exponential bounds for DPLL below the satisfiability threshold
- Cryptographic hardness of random local functions. Survey
- Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
- Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
- Hard satisfiable instances for DPLL-type algorithms
- Lower bounds for myopic DPLL algorithms with a cut heuristic
- The complexity of inverting explicit Goldreich's function by DPLL algorithms
- Non-interactive zero-knowledge in pairing-free groups from weaker assumptions
- On the algebraic immunity -- resiliency trade-off, implications for Goldreich's pseudorandom generator
- Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
- Locally computable UOWHF with linear shrinkage
- Automata, Languages and Programming
- Complexity results on DPLL and resolution
- The complexity of inversion of explicit Goldreich's function by DPLL algorithms
- Tight upper bound on splitting by linear combinations for pigeonhole principle
This page was built for publication: Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q862399)
