Ein effizienter Nachweis der Unerfüllbarkeit zufälliger 4-SAT-Formeln unter Verwendung der MAXCUT-Approximation
| Talking persons: |
| Frank Schädlich |
| Abstract: |
| 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. |
| Times: |
| part 1: Wednesday 25th June 2003, 9.15 am, room 1/368 part 2: Wednesday 9th July 2003, 9.15 am, room 1/368 |
