3-SAT
3-SAT ist ein klassisches Entscheidungsproblem der Informatik: Gegeben eine logische Formel in einer bestimmten Form, soll die Frage beantwortet werden, ob es eine Belegung der Variablen gibt, die die Formel erfüllt. 3-SAT gilt als eines der zentralen Beispiele für Probleme, die mit wachsender Eingabegröße scheinbar unlösbar schwer werden – und spielt deshalb in der Theoretischen Informatik und in der KI-Forschung eine Schlüsselrolle.
3-SAT ist ein Entscheidungsproblem: Man bekommt eine logische Formel, und die einzige Frage lautet « Ja oder Nein – gibt es eine Lösung? » Die Formel besteht aus Variablen, die entweder wahr oder falsch sein können, und aus Bedingungen, die gleichzeitig erfüllt sein müssen. Jede dieser Bedingungen enthält genau drei solcher Variablen – daher die Drei im Namen. Das Besondere: Niemand kennt einen schnellen Algorithmus, der diese Frage allgemein beantwortet. Für kleine Formeln ist das kein Problem. Aber sobald Hunderte oder Tausende von Variablen im Spiel sind, explodiert der Rechenaufwand.
Warum 3-SAT das Herzstück der Komplexitätstheorie ist
3-SAT gehört zu einer Klasse von Problemen, die Informatiker NP-vollständig nennen. Das bedeutet: Jedes andere Problem dieser Klasse lässt sich in 3-SAT umrechnen. Wer also einen schnellen Lösungsweg für 3-SAT findet, löst damit automatisch Tausende weiterer schwerer Probleme.
Darunter fallen praktisch relevante Aufgaben wie Stundenplanoptimierung, Routenplanung oder das Packen von Gütern in Container. All diese Probleme haben dieselbe Grundstruktur: viele Bedingungen, die gleichzeitig erfüllt sein sollen, aber keinen bekannten schnellen Weg zur Lösung. 3-SAT ist gewissermaßen ihr gemeinsamer Nenner.
Ob es je einen schnellen Algorithmus für NP-vollständige Probleme geben kann, ist die berühmteste offene Frage der Informatik – bekannt als das P-NP-Problem. Sie ist bis heute unbeantwortet, und für ihre Lösung hat das Clay Mathematics Institute eine Million Dollar ausgesetzt.
Aufbau einer 3-SAT-Formel
Eine 3-SAT-Formel sieht in vereinfachter Form so aus: « (A oder B oder nicht-C) und (nicht-A oder C oder D) und … ». Jede geklammerte Gruppe heißt Klausel und enthält genau drei Variablen. Das « und » zwischen den Klauseln bedeutet: Alle müssen gleichzeitig wahr sein. Innerhalb einer Klausel genügt es, wenn mindestens eine Variable wahr ist.
Eine Lösung – Informatiker sagen: eine erfüllende Belegung – ist eine Zuweisung von wahr oder falsch zu jeder Variable, sodass jede einzelne Klausel aufgeht. Das klingt einfach, solange man ein Dutzend Variablen hat. Bei hundert Variablen gibt es aber über eine Trillion mögliche Kombinationen. Sie alle durchzuprobieren ist selbst für schnelle Computer unrealistisch.
Moderne Löser, sogenannte SAT-Solver, nutzen clevere Abkürzungen: Sie schließen ganze Äste des Suchraums früh aus, sobald eine Teillösung schon eine Klausel verletzt. In der Praxis funktioniert das für viele reale Formeln überraschend gut – aber im schlechtesten Fall hilft auch das nicht.
3-SAT in der KI und im Alltag
SAT-Solver, die 3-SAT-ähnliche Formeln lösen, stecken in vielen Werkzeugen, die man nicht direkt sieht. Chip-Designer prüfen damit, ob ein Schaltkreis unter allen möglichen Eingaben korrekt funktioniert. Software-Prüfprogramme übersetzen Quellcode in logische Formeln und fragen dann einen SAT-Solver, ob ein Fehler rechnerisch möglich ist.
In der KI-Forschung taucht 3-SAT als Benchmark auf: Man erzeugt zufällige Formeln und misst, wie gut ein Algorithmus oder ein neuronales Netz damit zurechtkommt. Manche Forscher trainieren heute KI-Modelle darauf, SAT-Formeln zu lösen – nicht weil das der schnellste Weg wäre, sondern weil es zeigt, ob ein Modell überhaupt strukturiertes Schlussfolgern erlernen kann.
Wenn in Tech-News von « kombinatorischer Komplexität » oder davon die Rede ist, dass ein Problem « NP-schwer » sei, steckt hinter dieser Einschätzung fast immer eine Rückführung auf 3-SAT. Der Begriff ist damit nicht nur Lehrbuchstoff, sondern ein konkretes Werkzeug, mit dem Informatiker die Schwierigkeit neuer Probleme einordnen.