Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, September 25, 2008, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Dominik Scheder
Call a CNF formula *almost disjoint* if any two distinct clauses have at most one variable in common. What is the maximum integer m such that every almost disjoint k-CNF formula with m clauses is satisfiable? Denote this number by m(k). We prove pretty tight upper and lower bounds on m(k).
The upper bound uses a randomized construction of an unsatisfiable almost disjoint formula. We do not have any *explicit* construction that comes even close to the lower bound. However, we have certain arguments why a barehanded approach to constructing such formulas should always be difficult.
Automatic MiSe System Software Version 1.4803M | admin login