Approximate analysis of search algorithms with "physical" methods

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

An overview of some methods of statistical physics applied to the analysis of algorithms for optimization problems (satisfiability of Boolean constraints, vertex cover of graphs, decoding, ...) with distributions of random inputs is proposed. Two types of algorithms are analyzed: complete procedures with backtracking (Davis-Putnam-Loveland-Logeman algorithm) and incomplete, local search procedures (gradient descent, random walksat, ...). The study of complete algorithms makes use of physical concepts such as phase transitions, dynamical renormalization flow, growth processes, ... As for local search procedures, the connection between computational complexity and the structure of the cost function landscape is questioned, with emphasis on the notion of metastability.
28 pages, 23 figures

Keywords

Computational Complexity, Statistical Mechanics, F.2.2

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/31451

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0302003
 http://arxiv.org/abs/cs/0302003

Collections

arXiv