Schwere und Vollständigkeit (theoretische Informatik)

(Weitergeleitet von Satz von Shamir)

In der theoretischen Informatik – insbesondere in der Berechenbarkeits- und der Komplexitätstheorie – bezeichnet die Schwere (Übersetzung von engl. hardness dt. „Schwierigkeit“) 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   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   ein Mengensystem über den natürlichen Zahlen,   eine weitere Menge und schließlich   eine (berechenbarkeits- oder komplexitätstheoretische) Reduktion.

  • Das Problem   heiße  -schwer bezüglich  , falls gilt:  

Wenn sich also jedes Problem der Klasse   auf    -reduzieren lässt.

  •   heiße  -vollständig bezüglich   falls   zusätzlich selbst in   liegt.

Ist   eine Komplexitätsklasse, so 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 (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]

Beispiele

Bearbeiten
  • Stephen Cook zeigte 1971, dass das Erfüllbarkeitsproblem der Aussagenlogik   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   reduzieren lassen.
  • Eine Menge ist genau dann rekursiv aufzählbar, wenn sie sich many-one auf das Halteproblem   reduzieren lässt.   selbst liegt ebenfalls in RE, weshalb es RE-vollständig ist.
  • Da das spezielle Halteproblem   und das  -Halteproblem   rekursiv isomorph zu   sind, sind sie ebenfalls RE-vollständig.
  • Sowohl die Menge   aller totalen berechenbaren Funktionen als auch ihr Komplement sind RE-schwer aber nicht RE-vollständig.

Eigenschaften

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

Siehe auch

Bearbeiten

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