Springe zum Hauptinhalt
Fakultät für Informatik

194. Informatik-Kolloquium

Professur Theoretische Informatik


Dr. Olaf Beyersdorff


Institut für Elektrotechnik und Informatik
Universität Hannover

"Parametrisierte Beweiskomplexität"


Donnerstag, 12.07.2012
14.00 Uhr, 1/336

Alle interessierten Personen sind herzlich eingeladen!


We study the performance of DPLL algorithms on parameterized problems. In particular, we investigate how difficult it is to decide whether small solutions exist for satisfiability and other combinatorial problems. For this purpose we develop a Prover-Delayer game which models the running time of DPLL procedures and we establish an information-theoretic method to obtain lower bounds to the running time of parameterized DPLL procedures. We illustrate this technique by showing lower bounds to the parameterized pigeonhole principle and to the ordering principle. As our main application we study the DPLL procedure for the problem of deciding whether a graph has a small clique. We show that proving the absence of a k-clique requires $n^{\Omega(k)}$ steps for a non-trivial distribution of graphs close to the critical threshold.