https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=PolynomialzeitreduktionPolynomialzeitreduktion - Versionsgeschichte2026-06-05T12:35:47ZVersionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale KopieMediaWiki 1.43.8https://wiki-de.moshellshocker.dns64.de/index.php?title=Polynomialzeitreduktion&diff=86910&oldid=previmported>Felixsatr am 9. Dezember 2025 um 09:02 Uhr2025-12-09T09:02:16Z<p></p>
<p><b>Neue Seite</b></p><div>Eine '''Polynomialzeitreduktion''' (auch '''polynomielle Reduktion''') ist eine spezielle Form der [[Reduktion (Theoretische Informatik)|Reduktion]] in der [[Theoretische Informatik|theoretischen Informatik]]. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion [[Determinismus (Algorithmus)|deterministisch]] in [[Polynomialzeit]] berechnet werden kann.<br />
<br />
Polynomiell beschränkte [[Turingreduktion]]en werden (nach [[Stephen A. Cook]]) auch als '''Cook-Reduktion''' bezeichnet. Meist bezieht sich der Begriff Polynomialzeitreduktion jedoch auf eine polynomiell beschränkte [[Many-one-Reduktion]] (auch '''Karp-Reduktion''', nach [[Richard M. Karp]]).<br />
<br />
Polynomielle Many-one-Reduktionen werden in der [[Komplexitätstheorie]] beispielsweise verwendet, um nachzuweisen, dass eine Sprache der Komplexitätsklasse [[NP (Komplexitätsklasse)|NP]] auch [[NP-Vollständigkeit|NP-vollständig]] ist.<br />
<br />
Zwei Probleme heißen '''polynomiell äquivalent''', wenn von jedem eine Polynomialzeitreduktion auf das andere existiert.<br />
<br />
== Formale Definition ==<br />
Seien <math>L</math> und <math>L^\prime</math> zwei [[entscheidbar|Entscheidungsprobleme]] mit <math>L, L^\prime \subseteq \Sigma^*</math>.<br />
<br />
<math>L</math> ist polynomiell reduzierbar auf die Sprache <math>L^\prime</math>, wenn es eine in [[Polynomialzeit|polynomieller Zeit]] [[Berechenbarkeit|berechenbare]] Funktion <math>f\colon \Sigma^* \to \Sigma^*</math> gibt, so dass für alle Wörter <math>w \in \Sigma^*</math> die Äquivalenz <math>w \in L \Leftrightarrow f(w) \in L^\prime</math> gilt.<ref>Th. H. Cormen et al., ''Algorithmen - Eine Einführung'', MIT Press (2009), ISBN 3486590022, S. 1077</ref><br />
<br />
== Schreibweisen ==<br />
Es existieren unterschiedliche Schreibweisen, darunter<br />
: <math>L \preceq_p L^\prime</math><br />
: <math>L \le_{pol} L^\prime</math><br />
: <math>L \le_{p} L^\prime</math><br />
<br />
== Beispiel ==<br />
Wir zeigen <math>CLIQUE \le_{p} IS</math> durch die Angabe einer polynomiellen Reduktion des [[Cliquenproblem|CLIQUE-Problemes]] auf das [[Stabile Menge|Independent set]]-Problem.<br />
<br />
Ein Independent set ist eine Gruppe von Knoten, zwischen denen es paarweise keine Kanten gibt.<br />
<br />
Eine Clique ist eine Gruppe von Knoten, welche paarweise immer durch eine Kante verbunden sind.<br />
<br />
Deswegen hat ein Graph G genau dann eine CLIQUE der Größe k, wenn der [[Komplementgraph]] ein Independent set der Größe k hat.<br />
<br />
Den Komplementgraphen zu erstellen ist offensichtlich in polynomieller Zeit (gemessen in der Eingabegröße) möglich, da die [[Adjazenzmatrix]] genau einmal durchlaufen werden muss. Dadurch ist die gesamte Reduktion in polynomieller Zeit möglich.<br />
<br />
Also ist es möglich das Entscheidungsproblem, ob ein Graph G eine CLIQUE der Größe k hat, auf das Independent set Problem zu reduzieren. Aus der NP-Vollständigkeit von CLIQUE kann man durch diese Reduktion auf die NP-Vollständigkeit von Independent set schließen.<br />
<br />
== Quellen ==<br />
<references /><br />
<br />
[[Kategorie:Komplexitätstheorie]]<br />
<br />
[[he:רדוקציה חישובית]]</div>imported>Felixsatr