Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Solving satisfiability problems by fluctuations: the dynamics of stochastic local search algorithms
Ist Teil von
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics, 2003-06, Vol.67 (6 Pt 2), p.066104-066104, Article 066104
Ort / Verlag
United States
Erscheinungsjahr
2003
Quelle
PROLA
Beschreibungen/Notizen
Stochastic local search algorithms are frequently used to numerically solve hard combinatorial optimization or decision problems. We give numerical and approximate analytical descriptions of the dynamics of such algorithms applied to random satisfiability problems. We find two different dynamical regimes, depending on the number of constraints per variable: For low constraintness, the problems are solved efficiently, i.e., in linear time. For higher constraintness, the solution times become exponential. We observe that the dynamical behavior is characterized by a fast equilibration and fluctuations around this equilibrium. If the algorithm runs long enough, an exponentially rare fluctuation towards a solution appears.
Sprache
Englisch
Identifikatoren
ISSN: 1539-3755, 1063-651X
eISSN: 1095-3787
DOI: 10.1103/physreve.67.066104
Titel-ID: cdi_proquest_miscellaneous_71606900
Format
–
Weiterführende Literatur
Empfehlungen zum selben Thema automatisch vorgeschlagen von bX