1 Eine Klasse von Problemen in O(n²) Hoang Nguyen März 2002 Einführung In  dieser  Seminarausarbeitung  beweisen  wir  für  einige  Probleme,  dass  sie  mindestens  so schwer  sind  wie  das  folgende  Basisproblem:  Gibt  es  zu  einer  gegebenen  Menge  S  von  n ganzen Zahlen drei Elemente aus S, deren Summe 0 ist? Wir nennen solche Probleme 3SUM- hart. Der beste bekannte Algorithmus für 3SUM benötigt    (n²) Zeit, was auch für die grosse Klasse der 3SUM-harten Probleme eine unüberwindbare Barriere zu sein scheint. Die Suche nach  o(n²)  Lösungen  für  diese  Probleme  ist  hoffnungslos,  solange  das  Basisproblem  nicht schneller gelöst werden kann. 1  Reduktion Wir  setzen  die  Komplexitäten  zweier  Probleme  in  Relation,  wenn  ein  Problem  das  andere löst. Dies geschieht durch Transformation der Instanzen. Definition 1.1  Seien A und B Probleme. Wir sagen, dass A f(n)-lösbar durch B ist, genau dann  wenn  jede  Instanz  von  A  der  Grösse  n  durch  eine  konstante  Anzahl  Instanzen  (der Grösse  O(n))  von  B  und  O(f(n))  zusätzlicher  Zeit  (Transformationskosten)  gelöst  werden kann.  Wir  beschränken  uns  im  Folgendem  darauf,  jede  Instanz  aus  A  zu  jeweils  nur  einer Instanz aus B zu transformieren und notieren A<<_f(n)B. Für A<< _f(n)B und B<<_f(n)A nennen wir A und B f(n)-äquivalent und schreiben A==_f(n)B. Ist A f(n)-lösbar durch B, so ist B in gewisser Weise mindestens so schwer wie A. Das aus der Definition folgende Lemma macht dies explizit. Lemma 1.1  Seien f und g zwei Polynome und A<<_f(n)B. Sei )) ( (    n g O obere Schranke für B und )) ( ( ) ( n g O n f , dann ist )) ( (    n g O auch obere Schranke für A. Sei umgekehrt )) ( (    n g untere Schranke für A und )) ( ( ) ( n g o n f , dann ist )) ( (    n g auch untere Schranke für B. 2  Das Basisproblem Problem: 3SUM. Instanz: Eine Menge S von n ganzen Zahlen. Frage: Gibt es a,b,c     S mit a + b + c = 0 ? Der beste bekannte Algorithmus für 3SUM braucht    (n²) Zeit im Worst Case. 3SUM ist f(n)- lösbar  durch  viele  Probleme  (für  folgende  Reduktionen  genügen  Transformationsschranken f(n)=O(n log n) ). Diese sind mindestens so hart wie 3SUM.