Schwere und Vollständigkeit (theoretische Informatik)

Grundidee und Definition

Die Schwere eines Problems bedeutet in der theoretischen Informatik, dass es mindestens so schwer zu lösen ist wie jedes Problem einer betrachteten Klasse. Ein vollständiges Problem ist zusätzlich selbst Mitglied dieser Klasse und gehört damit zu ihren schwierigsten Problemen.

Schwere und Vollständigkeit werden meist für Entscheidungsprobleme untersucht: Es wird entschieden, ob ein Objekt eine bestimmte Eigenschaft besitzt. Durch Gödelisierung kann man solche Probleme als Teilmengen der natürlichen Zahlen \mathbb{N} auffassen; berechnet werden soll dann die charakteristische Funktion einer Teilmenge von \mathbb{N}. Die Begriffe lassen sich auch auf Such- und Optimierungsprobleme übertragen.

Seien \mathcal{C}\subseteq\mathcal{P}(\mathbb{N}) eine Problemklasse, A\subseteq\mathbb{N} ein Problem und \preceq eine Reduktion. A heißt \mathcal{C}-schwer bezüglich \preceq, wenn \forall C\in\mathcal{C}: C\preceq A gilt: Jedes Problem der Klasse lässt sich also auf A reduzieren. A heißt \mathcal{C}-vollständig bezüglich \preceq, wenn es \mathcal{C}-schwer ist und außerdem selbst in \mathcal{C} liegt. Bei Komplexitätsklassen betrachtet man meist nur Reduktionen, deren Aufwand innerhalb der Klasse liegt.

Übliche Bezeichnungen

Ist die verwendete Reduktion aus dem Zusammenhang klar oder unwichtig, wird sie oft nicht genannt. NP-Vollständigkeit bedeutet beispielsweise Vollständigkeit für die Klasse der nichtdeterministisch in Polynomialzeit lösbaren Probleme, bezüglich polynomiell zeitbeschränkter oder logarithmisch platzbeschränkter Many-one-Reduktionen. In diesem Fall sind beide Reduktionsarten äquivalent.

Mit „vollständig“ ohne Angabe einer Klasse ist besonders im englischen Sprachraum häufig Vollständigkeit für die rekursiv aufzählbaren Mengen gemeint, bezüglich Many-one- oder One-one-Reduktion. Auch diese beiden Reduktionen sind hierbei gleichwertig.

Wichtige Beispiele

Stephen Cook bewies 1971, dass das Erfüllbarkeitsproblem der Aussagenlogik SAT NP-vollständig ist. Richard Karp zeigte ein Jahr später NP-Vollständigkeit für 20 weitere Probleme.

Vollständige Probleme können auch zur Definition einer Klasse dienen: NP besteht aus genau den Problemen, die sich polynomiell zeitbeschränkt many-one auf SAT reduzieren lassen.

Eine Menge ist genau dann rekursiv aufzählbar, wenn sie sich many-one auf das Halteproblem H reduzieren lässt. Da H selbst in RE liegt, ist es RE-vollständig. Auch das spezielle Halteproblem K und das \varepsilon-Halteproblem H_0 sind RE-vollständig, weil sie rekursiv isomorph zu H sind.

Die Menge TOTAL aller totalen berechenbaren Funktionen und ihr Komplement sind RE-schwer, aber nicht RE-vollständig.

Folgerungen aus Reduktionen

Reduktionen \preceq sind Quasiordnungen auf \mathcal{P}(\mathbb{N}), also reflexiv und transitiv. \mathcal{C}-schwere Probleme sind obere Schranken der Klasse \mathcal{C}; \mathcal{C}-vollständige Probleme sind ihre Maxima bezüglich \preceq. Weil eine Quasiordnung nicht notwendigerweise antisymmetrisch ist, müssen solche Maxima nicht eindeutig sein.

Aus der Transitivität folgt: Ist A \mathcal{C}-schwer und gilt A\preceq B, dann ist auch B \mathcal{C}-schwer.

Nach dem Satz von Myhill ist eine Menge genau dann produktiv, wenn sie coRE-schwer ist. coRE enthält die Komplemente rekursiv aufzählbarer Mengen. Daraus folgt: Die kreativen Mengen sind genau die RE-vollständigen Mengen.

Wie sich Komplemente verhalten, hängt von der Reduktion ab. Unter Turing-Reduktion \preceq_T ist ein Problem genau dann \mathcal{C}-schwer, wenn es auch co\mathcal{C}-schwer ist. Unter Many-one-Reduktion \preceq_m ist ein Problem genau dann \mathcal{C}-schwer, wenn sein Komplement co\mathcal{C}-schwer ist.