Approximate analysis of search algorithms with "physical" methods

Details Approximate analysis of search algorithms with "physical" methods Approximate analysis of search algorithms with "physical" methods

2003-02-03

arxiv.org/abs/cs/0302003v1

Computer Science

Computational Complexity

28 pages, 23 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Approximate analysis of search algorithms with "physical" methods does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximate analysis of search algorithms with "physical" methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate analysis of search algorithms with "physical" methods will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-350239