## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, March 13, 2008, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Dominik Scheder

## How many conflicts does it need to be unsatisfiable?

A pair of clauses in a CNF formula constitutes a conflict if they contain complementary literals. For example, (x OR y) and (~x OR z) constitute a conflict, but (x OR y) and (x OR u) do not.

Clearly, an unsatisfiable CNF formula must have (many) conflicts. We try to determine this number for k-CNF formulas (i.e., where every clause has exactly k literals) as a function of k. So we ask the following question: What is the minimum number of conflicts in an unsatisfiable k-CNF formula?

A lower bound of 2^k and an upper bound of {2^k \choose 2} are pretty straight-forward. We will show that the number of conflicts is at least 2.3^k.

Joint work with Philipp Zumstein.

Back to Upcoming talks

Information for students and suggested topics for student talks