Hard satisfiable formulas for DPLL-type algorithms

Simple item page
dc.creatorNikolenko, Sergey I.
dc.date2003-01-15
dc.date.accessioned2026-07-07T03:19:21Z
dc.date.available2026-07-07T03:19:21Z
dc.descriptionWe 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.
dc.description9 pages
dc.identifierhttps://arxiv.org/abs/cs/0301012
dc.identifierhttp://arxiv.org/abs/cs/0301012
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31426
dc.subjectComputational Complexity
dc.subjectF.2.2
dc.titleHard satisfiable formulas for DPLL-type algorithms
dc.typetext

Files

Collections

arXiv