Christopher Moore, Universität von New Mexico und Santa Fe Institut
Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB),
Montag, 14. Juli 2003, 12:30 Uhr
Seminarraum 2006, EG Rundbau
Zusammenfassung
The classic notion of NP-completeness is a worst-case definition of
complexity, in which a problem is considered hard if a diabolical
"adversary" can construct hard examples. It says very little about
whether all, or even most, examples we will find in the real world are
hard. Indeed, for many NP-complete problems there are efficient
heuristics that work quite well in practice.
One way to approach this question is to look at random problems, where
interactions and constraints are chosen from some probability
distribution. While real-world problems are far from random, they at
least provide an alternative to the worst-case view; and we may be able to
approach the real world by considering more sophisticated probability
distributions that take various kinds of information into account.
In this talk I will show several techniques for proving that a solution to
a random problem exists with high probability, including rigorously
analyzing polynomial-time heuristics and bounding the mean and variance of
the number of solutions. As an example I will discuss recent work on the
phase transition in random k-Satisfiability, one of the celebrated
NP-complete problems of computer science, and possible connections to the
"replica trick" of statistical physics.
Kontakt:
Amin Coja-OghlanPostanschrift: Johann von Neumann-Haus Humboldt-Universität zu Berlin Institut für Informatik Rudower Chaussee 25 12489 Berlin
Tel. : (+49 30) 2093 3803 Fax : (+49 30) 2093 3191 e-mail : coja@informatik.hu-berlin.de
English