3SUM ist ein Entscheidungsproblem aus der theoretischen Informatik und der algorithmischen Geometrie. Gegeben ist eine Menge oder Folge von Zahlen; gefragt wird, ob drei paarweise verschiedene Elemente die Summe null haben. Das Problem dient als Standardbeispiel in der feingranularen Komplexitätstheorie, weil viele Probleme durch Reduktionen als mindestens so schwer wie 3SUM eingeordnet werden. Die Frage, ob 3SUM in echt subquadratischer Zeit für ein festes lösbar ist, gilt als offenes Problem.
Problemstellung
In der üblichen Formulierung erhält ein Algorithmus eine endliche Menge von n ganzen oder reellen Zahlen. Gesucht ist die Antwort auf die Frage, ob es drei verschiedene Elemente gibt, so dass
gilt. Bei einer Eingabe als Folge oder Array wird meist gefordert, dass die drei verwendeten Positionen verschieden sind; die Werte selbst können dabei gleich sein.
Eine äquivalente Variante fragt nach . Sie entsteht aus der Nullsummenform durch Vorzeichenwechsel einer der drei Mengen. Ebenfalls verbreitet ist die dreimengige Variante, bei der drei Mengen und gegeben sind und geprüft wird, ob , und mit existieren.
Algorithmen
Ein einfacher Algorithmus prüft alle Tripel und benötigt Zeit. Eine bessere Standardmethode sortiert die Eingabe zunächst und verwendet anschließend für jedes feste Element zwei Zeiger, die sich von links und rechts durch das sortierte Feld bewegen. Ist die Summe zu klein, wird der linke Zeiger erhöht; ist sie zu groß, wird der rechte Zeiger verringert. Dadurch ergibt sich nach dem Sortieren eine quadratische Laufzeit von .
Für ganzzahlige Eingaben kann auch eine Hashtabelle verwendet werden: Für jedes Paar wird geprüft, ob in der Eingabe vorkommt. Diese Methode erreicht bei geeigneter Implementierung erwartete Laufzeit , benötigt aber zusätzlichen Speicher.
Für bestimmte Rechenmodelle sind leicht subquadratische Verfahren bekannt. Baran, Demaine und Pătraşcu beschrieben subquadratische Algorithmen für ganzzahlige und rationale Eingaben auf verschiedenen RAM-Modellen. Grønlund und Pettie gaben später subquadratische Algorithmen im Real-RAM-Modell an und zeigten eine obere Schranke von für die Entscheidungsbaumkomplexität. Spätere Arbeiten verbesserten logarithmische Faktoren der Laufzeit.
Komplexität und 3SUM-Vermutung
Die sogenannte 3SUM-Vermutung besagt in einer verbreiteten Form, dass es keinen Algorithmus mit Laufzeit für ein festes gibt. Diese Vermutung bezieht sich auf echt subquadratische Algorithmen. Sie wird nicht durch Algorithmen widerlegt, die nur logarithmische Faktoren gegenüber einsparen.
Für eingeschränkte lineare Entscheidungsbäume bewies Jeff Erickson untere Schranken für lineare Erfüllbarkeitsprobleme. Für eine feste lineare Gleichung in Variablen zeigte er eine untere Schranke von in einem eingeschränkten Modell. Für 3SUM ergibt dies eine quadratische Schranke in diesem Modell. Spätere Arbeiten zeigten jedoch, dass für allgemeinere lineare Entscheidungsbäume deutlich niedrigere obere Schranken möglich sind.
3SUM-Härte
Ein Problem heißt 3SUM-schwer oder 3SUM-hart, wenn ein echt subquadratischer Algorithmus für dieses Problem einen echt subquadratischen Algorithmus für 3SUM implizieren würde. Der Begriff wurde von Anka Gajentaan und Mark H. Overmars eingeführt. Sie zeigten, dass mehrere Probleme der algorithmischen Geometrie in diesem Sinn 3SUM-schwer sind.
Zu den von Gajentaan und Overmars betrachteten Beispielen gehören unter anderem:
die Frage, ob drei Geraden in der Ebene einen gemeinsamen Schnittpunkt haben, bestimmte Trennbarkeitsprobleme für achsenparallele Strecken, Überdeckungsprobleme mit Streifen, Fragen zur Vereinigung von Dreiecken in der Ebene, ausgewählte Sichtbarkeits- und Bewegungsplanungsprobleme.
3SUM-Härte ist keine unbedingte untere Schranke. Sie liefert eine bedingte Aussage: Wird für ein 3SUM-schweres Problem ein echt subquadratischer Algorithmus gefunden, dann folgt daraus auch ein entsprechender Fortschritt für 3SUM.
Varianten und Verallgemeinerungen
Eine direkte Verallgemeinerung ist das k-SUM-Problem. Dabei wird gefragt, ob Elemente einer Eingabe eine vorgegebene Summe, meist null, ergeben. Solche Probleme stehen in Beziehung zu linearen Erfüllbarkeitsproblemen und linearen Degenerationstests.
Eine weitere Variante ist Convolution-3SUM. Dabei wird nicht nach beliebigen drei Elementen gesucht, sondern nach Indizes mit einer Faltungsbedingung, etwa . Diese Variante wurde in Reduktionen für dynamische Datenstrukturen und verwandte Probleme verwendet.
Bedeutung
3SUM wird vor allem als Referenzproblem für bedingte untere Schranken verwendet. In der algorithmischen Geometrie, bei Datenstrukturen, dynamischen Graphproblemen und Stringproblemen dienen Reduktionen von 3SUM dazu, die Schwierigkeit scheinbar unterschiedlicher Probleme miteinander zu vergleichen. Die Rolle ähnelt in diesem begrenzten Sinn der Verwendung von NP-Vollständigkeit, betrifft aber typischerweise Probleme, die bereits in polynomialer Zeit lösbar sind.
Einzelnachweise
Kategorie:Komplexitätstheorie