Geodesic
Hard satisfiable formulas for DPLL-type algorithms
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VII, Tome 293 (2002), pp. 139-148

Voir la notice de l'article provenant de la source Math-Net.Ru

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 probably satisfiable formulas are proven. 
@article{ZNSL_2002_293_a7,
     author = {S. I. Nikolenko},
     title = {Hard satisfiable formulas for {DPLL-type} algorithms},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {139--148},
     publisher = {mathdoc},
     volume = {293},
     year = {2002},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2002_293_a7/}
}
TY  - JOUR
AU  - S. I. Nikolenko
TI  - Hard satisfiable formulas for DPLL-type algorithms
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2002
SP  - 139
EP  - 148
VL  - 293
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2002_293_a7/
LA  - ru
ID  - ZNSL_2002_293_a7
ER  - 
%0 Journal Article
%A S. I. Nikolenko
%T Hard satisfiable formulas for DPLL-type algorithms
%J Zapiski Nauchnykh Seminarov POMI
%D 2002
%P 139-148
%V 293
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZNSL_2002_293_a7/
%G ru
%F ZNSL_2002_293_a7
S. I. Nikolenko. Hard satisfiable formulas for DPLL-type algorithms. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VII, Tome 293 (2002), pp. 139-148. http://geodesic.mathdoc.fr/item/ZNSL_2002_293_a7/