Berlin 2005 – scientific programme

Parts | Days | Selection | Search | Downloads | Help

DY: Dynamik und Statistische Physik

DY 42: Statistical Physics (General) II

DY 42.5: Talk

Tuesday, March 8, 2005, 15:15–15:30, TU H3010

Finding hard problems — •Wolfgang Barthel and Alexander K. Hartmann — Institut für Theoretische Physik, Universität Göttingen, http://www.theorie.physik.uni-goettingen.de/~barthel

Why is it often so difficult to find the optimal solution? To answer this question computer scientists classify problems according to their complexity, i. e. how fast a worst-case realization of the problem can be solved depending on its size.
The specific problem we consider is the vertex-cover problem: Take a random graph consisting of undirected edges that meet at vertices. A vertex cover is a subset of the vertices that contains at least one of the two end vertices of every edge. Finding the vertex cover of minimal size is a NP-complete problem, i.e. the challenge of developing a fast algorithm or proving its non-existence is still open.
Typically the solution time heavily depends on the specific realization. To gain insight in the hardness of the problem one would like to compare typical realizations with the ones harder to solve. We present the results of a Monte Carlo simulation in the space of instances. Here the logarithm of the solution time plays the role of the energy, so harder instances are more favorable at low “temperature” for the dynamics.