Restart method and exponential acceleration of random 3-SAT instances resolutions: a large deviation analysis of the Davis-Putnam-Loveland-Logemann algorithm

Simple item page
dc.creatorCocco, S.
dc.creatorMonasson, R.
dc.date2002-06-13
dc.date.accessioned2026-07-07T02:45:51Z
dc.date.available2026-07-07T02:45:51Z
dc.descriptionThe analysis of the solving complexity of random 3-SAT instances using the Davis-Putnam-Loveland-Logemann (DPLL) algorithm slightly below threshold is presented. While finding a solution for such instances demands exponential effort with high probability, we show that an exponentially small fraction of resolutions require a computation scaling linearly in the size of the instance only. We compute analytically this exponentially small probability of easy resolutions from a large deviation analysis of DPLL with the Generalized Unit Clause search heuristic, and show that the corresponding exponent is smaller (in absolute value) than the growth exponent of the typical resolution time. Our study therefore gives some quantitative basis to heuristic restart solving procedures, and suggests a natural cut-off cost (the size of the instance) for the restart.
dc.descriptionsubmitted to Annals of Math and Artificial Intelligence
dc.identifierhttps://arxiv.org/abs/cond-mat/0206242
dc.identifierhttp://arxiv.org/abs/cond-mat/0206242
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/19449
dc.subjectStatistical Mechanics
dc.subjectDisordered Systems and Neural Networks
dc.titleRestart method and exponential acceleration of random 3-SAT instances resolutions: a large deviation analysis of the Davis-Putnam-Loveland-Logemann algorithm
dc.typetext

Files

Collections

arXiv