Hard satisfiable formulas for DPLL-type algorithms
<|reference_start|>Hard satisfiable formulas for DPLL-type algorithms: We address lower bounds on the time complexity of algorithms solving the propositional satisfiability problem. Namely, we consider two DPLL-type algorithms, enhanced with the unit clause and pure literal heuristics. Exponential lower bounds for solving satisfiability on provably satisfiable formulas are proven.<|reference_end|>
@article{nikolenko2003hard,
    title={Hard satisfiable formulas for DPLL-type algorithms},
    author={Sergey I. Nikolenko},
    journal={arXiv preprint arXiv:cs/0301012},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0301012},
    primaryClass={cs.CC}
}