Kolloquiumsvortrag: Dr. Holger Dell, Uni Saarland

06.02.2015 von 14:15 bis 15:45

LMS 2 Ü2/K

Title: The strong exponential time hypothesis
The fastest known algorithm for CNF-SAT, the satisfiability problem for formulas in conjunctive normal form, runs in time roughly 2^{n - o(n)}, where n is the number of variables; this is not much faster than exhaustive search. The strong exponential time hypothesis (Strong ETH) asserts that this is essentially best possible, that is, CNF-SAT cannot be solved in time 1.99^n. One of the reasons why this hypothesis is so interesting is that we don't have a clear sense for whether it is true or not, and it is quite possible that a clever algorithm could be found that solves CNF-SAT in time 1.99^n. This talk will survey results related to Strong ETH. In particular, we will see reductions from CNF-SAT to other problems, which establish tight running time lower bounds if the Strong ETH is true. Surprisingly, the Strong ETH can not only be used to rule out running times of the form 1.99^n for some problems, but it is also able to rule out running times of the form n^1.99 for certain problems that can be solved in time n^2. Finally, we will also discuss SAT-algorithms and techniques that could eventually refute Strong ETH.



Prof. Dr. Klaus Jansen

Diesen Termin meinem iCal-Kalender hinzufügen