2 Definition 2.1  Wir nennen ein Problem A 3SUM-hart, genau dann wenn 3SUM f(n)-lösbar durch A ist, d.h. 3SUM<<_f(n)A. Dabei ist f(n) = o(n²). Zur Durchführung von Reduktionen definieren wir ein äquivalentes    asisproblem: Problem: 3SUM’. Instanz: Drei Mengen A, B, C von insgesamt n ganzen Zahlen.   Frage: Gibt es drei Zahlen a   A, b   B, c   C mit a + b = c ? Theorem 2.1  3SUM’==_n3SUM. Beweis:  3SUM<< _n3SUM’ ist trivial. Wir setzen einfach A=S, B=S, C=-S. Wenn a+b=c mit a   A,  b   B,  c   C  gilt,  dann  ist  offensichtlich  a   S,  b   S,  (-c)   S  und  a+b+(-c)=0.  Für  die Umkehrung konstruieren wir eine Menge S, zu der es wenn 3 Elemente in der Summe 0 sind, 3 Elemente a   A, b   B und c   C gibt, so dass a+b=c. Ohne Einschränkung seien A, B und C positiv (sonst bilde A+k, B+k und C+2k mit passender Konstante k). Sei m=2*max(A,B,C). Zu allen Elementen a   A, b   B, c   C konstruieren wir Elemente a’=a+m, b’=b und c’=-c-m für S. Wenn a+b=c dann a’+b’+c’=0, wir müssen nur noch einsehen, dass a, b und c aus drei verschiedenen Mengen sind. Dies folgt aus der Konstruktion von S. ! 3SUM’  (und  somit  3SUM)  kann  in  O(n²)  gelöst  werden:  Sortiere  die  Mengen  B  und  C. Berechne für jedes a   A die sortierte Menge B+a (plus a zu allen Elementen) in jeweils O(n) und suche dann in O(n) ein gemeinsames Element in B+a und C. Da wir dies mit allen O(n) Elementen a   A wiederholen, ist die Laufzeit durch O(n²) beschränkt. Die geometrische Interpretation des Basisproblems wird Reduktionen erleichtern. Problem: GeomBase. Instanz: Eine Menge von n Punkten mit ganzzahligen Koordinaten    auf drei Geraden y=0, y=1 und y=2. Frage: Gibt es eine nicht horizontale Gerade durch 3 dieser Punkte ? Theorem 2.2  GeomBase==_n3SUM’. Beweis:  Zuerst zeigen wir 3SUM’<<_nGeomBase. Wir erzeugen für alle Element a   A, b   B und c   C die Punkte (a,0), (b,2) bzw. (c/2,1). Offensichtlich sind drei Punkte (a,0), (b,2) und (c/2,1) kolinear genau dann wenn a+b=c. Für die Umkehrung erzeugen wir zu jedem Punkt (a,0) ein Element a   A, zu jedem Punkt (b,2) ein Element b   B und zu jedem Punkt (c,1) ein Element 2c   C. ! B C/2 A Figur 1:  Ein Beispiel für GeomBase. · · · · · · · · · · · · · · · ·