Schwere und Vollständigkeit (theoretische Informatik)

Schwere und Vollständigkeit werden üblicherweise nur für Entscheidungsprobleme betrachtet. Bei diesen wird gefragt, ob einem bestimmten Objekt eine besondere Eigenschaft zukommt oder nicht. Genauer genügt es sogar – durch eine geeignete Gödelisierung – ausschließlich Entscheidungsprobleme von Mengen natürlicher Zahlen zu betrachten. Das Ziel ist also stets die charakteristische Funktion einer Teilmenge von ${\displaystyle \mathbb {N} }$ zu berechnen. Dieser Ansatz hat den Vorteil, dass nun die Probleme mit den Teilmengen selbst identifiziert werden können. Es ist aber sehr leicht möglich die folgenden Definitionen auch auf Optimierungs- und Suchprobleme zu übertragen.

Sei daher nun ${\displaystyle {\mathcal {C}}\subseteq {\mathcal {P}}(\mathbb {N} )}$ ein Mengensystem über den natürlichen Zahlen, ${\displaystyle A\subseteq \mathbb {N} }$ eine weitere Menge und schließlich ${\displaystyle \preceq }$ eine (berechenbarkeits- oder komplexitätstheoretische) Reduktion.

• Das Problem ${\displaystyle A}$ heiße ${\displaystyle {\mathcal {C}}}$-schwer bezüglich ${\displaystyle \preceq }$, falls gilt: ${\displaystyle \forall C\in {\mathcal {C}}\colon C\preceq A}$

Wenn sich also jedes Problem der Klasse ${\displaystyle {\mathcal {C}}}$ auf ${\displaystyle A}$ ${\displaystyle \preceq }$-reduzieren lässt.

• ${\displaystyle A}$ heiße ${\displaystyle {\mathcal {C}}}$-vollständig bezüglich ${\displaystyle \preceq }$ falls ${\displaystyle A}$ zusätzlich selbst in ${\displaystyle {\mathcal {C}}}$ liegt.

Ist ${\displaystyle {\mathcal {C}}}$ eine Komplexitätsklasse, so werden meist nur solche Reduktionen betrachtet, deren Berechnungsaufwand noch innerhalb der Klasse selbst liegt.

Wenn es aus dem Zusammenhang klar bzw. unerheblich ist, um welche Reduktion es sich handelt, wird diese in der Notation auch häufig weggelassen. So bedeutet beispielsweise der Begriff NP-Vollständigkeit, dass ein Problem vollständig für die Komplexitätsklasse aller nicht-deterministisch in Polynomialzeit lösbaren Probleme bezüglich der polynomiell zeitbeschränkten oder der logarithmisch platzbeschränkten Many-one-Reduktion ist. Diese abkürzende Schreibweise ist möglich, da in diesem speziellen Fall die beiden Reduktionsarten äquivalent sind.

Gelegentlich wird sogar die Angabe der betrachteten Problemklasse unterdrückt, so steht vor allem im englischen Sprachraum vollständig (englisch complete) für die Eigenschaft eines Problems, vollständig für die Klasse der rekursiv aufzählbaren Mengen bezüglich der Many-one- bzw. der One-one-Reduktion zu sein. Auch hier sind die beiden betrachteten Reduktionen gleichwertig.[2]

• Stephen Cook zeigte 1971, dass das Erfüllbarkeitsproblem der Aussagenlogik ${\displaystyle SAT}$ NP-vollständig ist, darauf aufbauend wies Richard Karp ein Jahr später diese Eigenschaft noch für 20 weitere Probleme nach.
• Umgekehrt lassen sich Problemklassen auch dadurch definieren, dass man ein für sie vollständiges Problem (bezüglich einer bestimmten Reduktion) angibt. So ist die Komplexitätsklasse NP die Gesamtheit aller Probleme, die sich polynomiell zeitbeschränkt many-one auf ${\displaystyle SAT}$ reduzieren lassen.
• Eine Menge ist genau dann rekursiv aufzählbar, wenn sie sich many-one auf das Halteproblem ${\displaystyle H}$ reduzieren lässt. ${\displaystyle H}$ selbst liegt ebenfalls in RE, weshalb es RE-vollständig ist.
• Da das spezielle Halteproblem ${\displaystyle K}$ und das ${\displaystyle \varepsilon }$-Halteproblem ${\displaystyle H_{0}}$ rekursiv isomorph zu ${\displaystyle H}$ sind, sind sie ebenfalls RE-vollständig.
• Sowohl die Menge ${\displaystyle TOTAL}$ aller totalen berechenbaren Funktionen als auch ihr Komplement sind RE-schwer aber nicht RE-vollständig.

• Die Reduktionen ${\displaystyle \preceq }$ bilden Quasiordnungen auf der Menge ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ aller Probleme. Die ${\displaystyle {\mathcal {C}}}$-schweren Probleme sind dann gerade die oberen Schranken und die ${\displaystyle {\mathcal {C}}}$-vollständigen Probleme die Maxima der Klasse ${\displaystyle {\mathcal {C}}}$ bezüglich ${\displaystyle \preceq }$. Dabei ist zu beachten, dass auf Grund der fehlenden Antisymmetrie von ${\displaystyle \preceq }$ die Maxima nicht notwendig eindeutig sein müssen.
  • Insbesondere sind Reduktionen transitiv. Ist also ein Problem ${\displaystyle A}$ schwer bzgl. ${\displaystyle \preceq }$ für die Klasse ${\displaystyle {\mathcal {C}}}$ und gilt zusätzlich ${\displaystyle A\preceq B}$ für ein weiteres Problem, so ist dieses ebenfalls ${\displaystyle {\mathcal {C}}}$-schwer.
• Eine Menge ist genau dann produktiv, wenn sie coRE-schwer ist, dies ist der Satz von Myhill.[3] Die Berechenbarkeitsklasse coRE enthält dabei gerade die Komplemente rekursiv aufzählbarer Mengen.
  • Daraus folgt, dass die kreativen Mengen genau die RE-vollständigen sind.
• Im Allgemeinen hängt das Verhalten von komplementären Klassen bzw. Problemen von der gewählten Reduktion ab:
  • Unter der Turing-Reduktion ${\displaystyle \preceq _{T}}$ ist bspw. ein Problem genau dann ${\displaystyle {\mathcal {C}}}$-schwer, wenn es auch ${\displaystyle co{\mathcal {C}}}$-schwer ist.
  • Unter der Many-One-Reduktion ${\displaystyle \preceq _{m}}$ dagegen ist ein Problem genau dann ${\displaystyle {\mathcal {C}}}$-schwer, wenn sein Komplement ${\displaystyle co{\mathcal {C}}}$-schwer ist.

• NP-Schwere
• NP-Vollständigkeit

1. E. Post: Recursively enumerable sets of positive integers and their decision problems. Bulletin of the American Mathematical Society, vol. 50 (1944), no. 5, pp. 284–316 (online, PDF-Datei; 4,0 MB)
2. H. Rogers jr.: Theory of recursive functions and effective computability. 2nd ed., 3rd printing (1992), MIT Press, Cambridge MA, ISBN 0-262-68052-1 - §7.5 Theorem VII, p. 87
3. J. Myhill: Creative sets. In: Zeitschrift für Mathematische Logik und Grundlagen der Mathematik Ausg. 1 (1955), S. 97–108