Polynomialzeitreduktion

Eine Polynomialzeitreduktion (auch polynomielle Reduktion) ist eine spezielle Form der Reduktion in der theoretischen Informatik. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann.

Polynomiell beschränkte Turingreduktionen 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 auch NP-vollständig ist.

Formale Definition

Seien $L$ und $L^{\prime }$ zwei Entscheidungsprobleme mit $L,L^{\prime }\subseteq \Sigma ^{*}$.

$L$ ist polynomiell reduzierbar auf die Sprache $L^{\prime }$, wenn es eine in polynomieller Zeit berechenbare Funktion $f\colon \Sigma ^{*}\to \Sigma ^{*}$ gibt, so dass für alle Wörter $w\in \Sigma ^{*}$ die Äquivalenz $w\in L\Leftrightarrow f(w)\in L^{\prime }$ gilt.

Schreibweisen

Es existieren unterschiedliche Schreibweisen, darunter

$L\preceq _{p}L^{\prime }$

$L\leq _{pol}L^{\prime }$

$L\leq _{p}L^{\prime }$

Beispiel

Wir zeigen $CLIQUE\leq _{p}IS$ durch die Angabe einer polynomiellen Reduktion des CLIQUE-Problemes auf das 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.