Schwere und Vollständigkeit (Theoretische Informatik)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der theoretischen Informatik - insbesondere in der Berechenbarkeits- und der Komplexitätstheorie - bezeichnet die Schwere (nach einer Fehlübersetzung von engl. hardness auch Härte) eines Problems dessen Eigenschaft, mindestens so schwierig lösbar zu sein wie alle Probleme einer betrachteten Klasse. Die Vollständigkeit eines Problems bedeutet dann, dass es sich um ein schwierigstes Problem aus dieser Klasse handelt. Anschaulich gesprochen kann also ein Algorithmus, der ein schweres Problem lösen kann, mit nur geringen Modifikationen auch alle Probleme der entsprechenden Klasse lösen.

Die Idee, Probleme nach ihrer Lösbarkeit zu vergleichen und dabei schwere und vollständige Probleme zu untersuchen, geht auf einen Aufsatz von Emil Post aus dem Jahr 1944 zurück.[1]

Definitionen[Bearbeiten]

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 \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 \mathcal C \subseteq \mathcal P(\N) ein Mengensystem über den natürlichen Zahlen, A \subseteq \N eine weitere Menge und schließlich \preceq eine (berechenbarkeits- oder komplexitätstheoretische) Reduktion.

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

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

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

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

Sprechweise[Bearbeiten]

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 (engl. 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]

Beispiele[Bearbeiten]

Eigenschaften[Bearbeiten]

  • Die Reduktionen \preceq bilden Quasiordnungen auf der Menge \mathcal{P}(\N) aller Probleme. Die \mathcal{C}-schweren Probleme sind dann gerade die oberen Schranken und die \mathcal{C}-vollständigen Probleme die Maxima der Klasse \mathcal{C} bezüglich \preceq. Dabei ist zu beachten, dass auf Grund der fehlenden Antisymmetrie von \preceq die Maxima nicht notwendig eindeutig sein müssen.
    • Insbesondere sind Reduktionen transitiv. Ist also ein Problem A schwer bzgl. \preceq für die Klasse \mathcal{C} und gilt zusätzlich A \preceq B für ein weiteres Problem, so ist dieses ebenfalls \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 \preceq_T ist bspw. ein Problem genau dann \mathcal{C}-schwer, wenn es auch co \mathcal{C}-schwer ist.
    • Unter der Many-One-Reduktion \preceq_m dagegen ist ein Problem genau dann \mathcal{C}-schwer, wenn sein Komplement co \mathcal{C}-schwer ist.

Einzelnachweise[Bearbeiten]

  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. Rodgers 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

Siehe auch[Bearbeiten]