Dresden 2003 – scientific programme

Parts | Days | Selection | Search | Downloads | Help

DY: Dynamik und Statistische Physik

DY 53: Statistical physics (general) II

DY 53.5: Talk

Friday, March 28, 2003, 12:30–12:45, G\"OR/229

Solving satisfiability problems by fluctuations: A description of the dynamics of stochastic local search algorithms — •Wolfgang Barthel, Alexander K. Hartmann, and Martin Weigt — Institut f. Theoretische Physik, Bunsenstr. 9, 37073 Göttingen

Hard combinatorical optimization problems play an important role in Theoretical Computer Science. One is especially interested in the time complexity of such problems, i. e. how fast a typical instance can be solved depending on its size. To find solutions to these problems stochastic local search algorithms are frequently used. Their running time heavily depends on the structure of the solution space which is often very complex in one region while being relatively simple in another.

We analytically and numerically study the dynamics of such algorithms applied to random satisfiability problems. Instances of these problems are boolean formulas which impose constraints on its variables We find that for low constraintness, the problems are solved efficiently, i.e. in linear time. For higher constraintness, the solution time becomes exponential. We observe that in this case the algorithm spends most of the time in regions seperated from the solution by entropic barriers. If the algorithm runs long enough, exponentially rare fluctuations towards a solution appear.