Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
From MaRDI portal
(Redirected from Publication:862399)
Recommendations
Cites work
- scientific article; zbMATH DE number 1445296 (Why is no real title available?)
- scientific article; zbMATH DE number 6469161 (Why is no real title available?)
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- A sharp threshold in proof complexity
- Exponential bounds for DPLL below the satisfiability threshold
- Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
- Lower bounds for polynomial calculus in the case of nonbinomial ideals.
- Pseudorandom Generators in Propositional Proof Complexity
- SAT local search algorithms: Worst-case study
- Short proofs are narrow—resolution made simple
- Toward a model for backtracking and dynamic programming
Cited in
(32)- Tight upper bound on splitting by linear combinations for pigeonhole principle
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- On exponential time lower bound of Knapsack under backtracking
- scientific article; zbMATH DE number 1445296 (Why is no real title available?)
- 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
- On linear-size pseudorandom generators and hardcore functions
- Exponential lower bounds for DPLL algorithms on satisfiable random 3-CNF formulas
- 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
- Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
- On the algebraic immunity -- resiliency trade-off, implications for Goldreich's pseudorandom generator
- 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
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)
