Ein effizienter Nachweis der Unerfüllbarkeit zufälliger 4-SAT-Formeln unter Verwendung der MAXCUT-Approximation
| Vortragende(r): |
| Frank Schädlich |
| Inhalt: |
| Es wird ein Polynomialzeitalgorithmus vorgestellt, der für fast alle zufälligen 4-SAT-Formeln mit n Variablen und 117⋅n2 Klauseln die Unerfüllbarkeit nachweist. Der Algorithmus verwendet die MAXCUT-Approximation von Goemans und Williamson (1995). Hierdurch ist es möglich, das Resultat von Goerdt und Krivelevich (2001) zu verbessern. Der von Goerdt und Krivelevich beschriebene Polynomialzeitalgorithmus benötigt Poly(log n)⋅n2 Klauseln. |
| Zeiten: |
| Teil 1: Mittwoch, der 25.06.2003, 09:15 Uhr, Raum 1/368 Teil 2: Mittwoch, der 09.07.2003, 09:15 Uhr, Raum 1/368 |
