Quelltext der Seite Polynomialzeitreduktion

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.

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

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.

Zwei Probleme heißen '''polynomiell äquivalent''', wenn von jedem eine Polynomialzeitreduktion auf das andere existiert.

== Formale Definition ==
Seien <math>L</math> und <math>L^\prime</math> zwei [[entscheidbar|Entscheidungsprobleme]] mit <math>L, L^\prime \subseteq \Sigma^*</math>.

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

== Schreibweisen ==
Es existieren unterschiedliche Schreibweisen, darunter
: <math>L \preceq_p L^\prime</math>
: <math>L \le_{pol} L^\prime</math>
: <math>L \le_{p} L^\prime</math>

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

Ein Independent set ist eine Gruppe von Knoten, zwischen denen es paarweise keine Kanten gibt.

Eine Clique ist eine Gruppe von Knoten, welche paarweise immer durch eine Kante verbunden sind.

Deswegen hat ein Graph G genau dann eine CLIQUE der Größe k, wenn der [[Komplementgraph]] ein Independent set der Größe k hat.

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.

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.

== Quellen ==
<references />

[[Kategorie:Komplexitätstheorie]]

[[he:רדוקציה חישובית]]