Loading AI tools
Aus Wikipedia, der freien Enzyklopädie
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]
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.
Wenn sich also jedes Problem der Klasse auf -reduzieren lässt.
Ist 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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.