2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/31426We 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.9 pagesComputational ComplexityF.2.2text