|
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.
| |
|