Polynomialzeitreduktion

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Karp-Reduktion)
Zur Navigation springen Zur Suche springen

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

[Bearbeiten | Quelltext bearbeiten]

Seien und zwei Entscheidungsprobleme mit .

ist polynomiell reduzierbar auf die Sprache , wenn es eine in polynomieller Zeit berechenbare Funktion gibt, so dass für alle Wörter die Äquivalenz gilt.[1]

Es existieren unterschiedliche Schreibweisen, darunter

Wir zeigen 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.

  1. Th. H. Cormen et al., Algorithmen - Eine Einführung, MIT Press (2009), ISBN 3486590022, S. 1077