Wykład z informatyki im. Mariana Rejewskiego, Jerzego Różyckiego, Henryka Zygalskiego 2010

Data: piątek, 28.05.2010, godz. 11:00

Prelegent: prof. Emo Welzl

Tytuł: When Conflicting Constraints Can be Resolved - the Local Lemma and Satisfiability

Abstrakt: The general theme underlying the talk is the following question: Given a set of constraints, how much interleaving of these constraints (relative to how serious these constraints are) is necessary so that all of them cannot be satisfied simultaneously?

For a concrete setting we consider boolean formulas in conjunctive normal form (CNF), where the clauses play the role of constraints. If all clauses are large, it needs many clauses to obtain an unsatisfiable formula; moreover, these clauses have to interleave. We review quantitative results for the amount of interleaving required, many of which rely on the Lovász Local Lemma, a probabilistic lemma with many applications in combinatorics.

In positive terms, we are interested in simple combinatorial conditions which guarantee for a CNF formula to be satisfiable. The criteria obtained are nontrivial in the sense that even though they are easy to check, it is by far not obvious how to compute a satisfying assignment efficiently in case the conditions are fulfilled; until recently, it was not known how to do so. It is also remarkable that while deciding satisfiability is trivial for formulas that satisfy the conditions, a slightest relaxation of the conditions leads us into the territory of NP-completeness.

Wideo

Program

Prelegent

Emo Welzl - profesor Eidgenössische Technische Hochschule w Zurichu (ETH); jego badania dotyczą między innymi geometrii obliczeniowej, optymalizacyjnych modeli kombinatorycznych, analizy struktur geometrycznych, geometrii dyskretnej, metod probabilistycznych a ostatnio także spełnialności; laureat Max Planck Prize oraz Gottfried Wilhelm Leibniz-Prize; członek Deutsche Akademie der Naturforscher Leopoldina.