www.wikidata.de-de.nina.az

Schwere und Vollständigkeit theoretische Informatik In der theoretischen Informatik insbesondere in der Berechenbarkeits

Schwere und Vollständigkeit (theoretische Informatik)

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.

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.

Beispiele Bearbeiten

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. 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
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der theoretischen Informatik insbesondere in der Berechenbarkeits und der Komplexitatstheorie bezeichnet die Schwere Ubersetzung von engl hardness dt Schwierigkeit eines Problems dessen Eigenschaft mindestens so schwierig losbar zu sein wie alle Probleme einer betrachteten Klasse Die Vollstandigkeit 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 losen kann mit nur geringen Modifikationen auch alle Probleme der entsprechenden Klasse losen Die Idee Probleme nach ihrer Losbarkeit zu vergleichen und dabei schwere und vollstandige Probleme zu untersuchen geht auf einen Aufsatz von Emil Post aus dem Jahr 1944 zuruck 1 Inhaltsverzeichnis 1 Definitionen 2 Sprechweise 3 Beispiele 4 Eigenschaften 5 Siehe auch 6 EinzelnachweiseDefinitionen BearbeitenSchwere und Vollstandigkeit werden ublicherweise nur fur Entscheidungsprobleme betrachtet Bei diesen wird gefragt ob einem bestimmten Objekt eine besondere Eigenschaft zukommt oder nicht Genauer genugt es sogar durch eine geeignete Godelisierung ausschliesslich Entscheidungsprobleme von Mengen naturlicher Zahlen zu betrachten Das Ziel ist also stets die charakteristische Funktion einer Teilmenge von N displaystyle mathbb N nbsp zu berechnen Dieser Ansatz hat den Vorteil dass nun die Probleme mit den Teilmengen selbst identifiziert werden konnen Es ist aber sehr leicht moglich die folgenden Definitionen auch auf Optimierungs und Suchprobleme zu ubertragen Sei daher nun C P N displaystyle mathcal C subseteq mathcal P mathbb N nbsp ein Mengensystem uber den naturlichen Zahlen A N displaystyle A subseteq mathbb N nbsp eine weitere Menge und schliesslich displaystyle preceq nbsp eine berechenbarkeits oder komplexitatstheoretische Reduktion Das Problem A displaystyle A nbsp heisse C displaystyle mathcal C nbsp schwer bezuglich displaystyle preceq nbsp falls gilt C C C A displaystyle forall C in mathcal C colon C preceq A nbsp Wenn sich also jedes Problem der Klasse C displaystyle mathcal C nbsp auf A displaystyle A nbsp displaystyle preceq nbsp reduzieren lasst A displaystyle A nbsp heisse C displaystyle mathcal C nbsp vollstandig bezuglich displaystyle preceq nbsp falls A displaystyle A nbsp zusatzlich selbst in C displaystyle mathcal C nbsp liegt Ist C displaystyle mathcal C nbsp eine Komplexitatsklasse so werden meist nur solche Reduktionen betrachtet deren Berechnungsaufwand noch innerhalb der Klasse selbst liegt Sprechweise BearbeitenWenn es aus dem Zusammenhang klar bzw unerheblich ist um welche Reduktion es sich handelt wird diese in der Notation auch haufig weggelassen So bedeutet beispielsweise der Begriff NP Vollstandigkeit dass ein Problem vollstandig fur die Komplexitatsklasse aller nicht deterministisch in Polynomialzeit losbaren Probleme bezuglich der polynomiell zeitbeschrankten oder der logarithmisch platzbeschrankten Many one Reduktion ist Diese abkurzende Schreibweise ist moglich da in diesem speziellen Fall die beiden Reduktionsarten aquivalent sind Gelegentlich wird sogar die Angabe der betrachteten Problemklasse unterdruckt so steht vor allem im englischen Sprachraum vollstandig englisch complete fur die Eigenschaft eines Problems vollstandig fur die Klasse der rekursiv aufzahlbaren Mengen bezuglich der Many one bzw der One one Reduktion zu sein Auch hier sind die beiden betrachteten Reduktionen gleichwertig 2 Beispiele BearbeitenStephen Cook zeigte 1971 dass das Erfullbarkeitsproblem der Aussagenlogik S A T displaystyle SAT nbsp NP vollstandig ist darauf aufbauend wies Richard Karp ein Jahr spater diese Eigenschaft noch fur 20 weitere Probleme nach Umgekehrt lassen sich Problemklassen auch dadurch definieren dass man ein fur sie vollstandiges Problem bezuglich einer bestimmten Reduktion angibt So ist die Komplexitatsklasse NP die Gesamtheit aller Probleme die sich polynomiell zeitbeschrankt many one auf S A T displaystyle SAT nbsp reduzieren lassen Eine Menge ist genau dann rekursiv aufzahlbar wenn sie sich many one auf das Halteproblem H displaystyle H nbsp reduzieren lasst H displaystyle H nbsp selbst liegt ebenfalls in RE weshalb es RE vollstandig ist Da das spezielle Halteproblem K displaystyle K nbsp und das e displaystyle varepsilon nbsp Halteproblem H 0 displaystyle H 0 nbsp rekursiv isomorph zu H displaystyle H nbsp sind sind sie ebenfalls RE vollstandig Sowohl die Menge T O T A L displaystyle TOTAL nbsp aller totalen berechenbaren Funktionen als auch ihr Komplement sind RE schwer aber nicht RE vollstandig Eigenschaften BearbeitenDie Reduktionen displaystyle preceq nbsp bilden Quasiordnungen auf der Menge P N displaystyle mathcal P mathbb N nbsp aller Probleme Die C displaystyle mathcal C nbsp schweren Probleme sind dann gerade die oberen Schranken und die C displaystyle mathcal C nbsp vollstandigen Probleme die Maxima der Klasse C displaystyle mathcal C nbsp bezuglich displaystyle preceq nbsp Dabei ist zu beachten dass auf Grund der fehlenden Antisymmetrie von displaystyle preceq nbsp die Maxima nicht notwendig eindeutig sein mussen Insbesondere sind Reduktionen transitiv Ist also ein Problem A displaystyle A nbsp schwer bzgl displaystyle preceq nbsp fur die Klasse C displaystyle mathcal C nbsp und gilt zusatzlich A B displaystyle A preceq B nbsp fur ein weiteres Problem so ist dieses ebenfalls C displaystyle mathcal C nbsp schwer Eine Menge ist genau dann produktiv wenn sie coRE schwer ist dies ist der Satz von Myhill 3 Die Berechenbarkeitsklasse coRE enthalt dabei gerade die Komplemente rekursiv aufzahlbarer Mengen Daraus folgt dass die kreativen Mengen genau die RE vollstandigen sind Im Allgemeinen hangt das Verhalten von komplementaren Klassen bzw Problemen von der gewahlten Reduktion ab Unter der Turing Reduktion T displaystyle preceq T nbsp ist bspw ein Problem genau dann C displaystyle mathcal C nbsp schwer wenn es auch c o C displaystyle co mathcal C nbsp schwer ist Unter der Many One Reduktion m displaystyle preceq m nbsp dagegen ist ein Problem genau dann C displaystyle mathcal C nbsp schwer wenn sein Komplement c o C displaystyle co mathcal C nbsp schwer ist Siehe auch BearbeitenNP Schwere NP VollstandigkeitEinzelnachweise Bearbeiten 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 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 J Myhill Creative sets In Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik Ausg 1 1955 S 97 108 Abgerufen von https de wikipedia org w index php title Schwere und Vollstandigkeit theoretische Informatik amp oldid 210631798