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.[1]

Schreibweisen

Es existieren unterschiedliche Schreibweisen, darunter

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

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

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

Quellen

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

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