One distinguished between easy and hard Optimization problems. For the first type very fast algorithms are available, but not for the second. Of particular interest are NP-hard problems, where the question of whether fast algorithms do exists is still open.

Recently it was found, that many of these problems exhibits phase transitions, which often coincide with drastical changes of the computing time.
Many NP-hard problems are important in theoretical computer science as well as for practical applications. In the research group, we are particluary interested in vertex covers of graphs and in the satisfiability of boolean formulas.

Recently it was found, that many of these problems exhibits phase transitions, which often coincide with drastical changes of the computing time. By mapping onto physical systems like spin glasses or lattice gases one can learn more about these problems than when using other approaches. Furthermore, this better understanding allows to find more efficient algorithms, which then can be applied for practical applications.