Polynomialzeitreduktion

Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Eine Polynomialzeitreduktion (auch als polynomielle Reduktion bezeichnet) ist eine spezielle Form der Reduktion .

Neben der Forderung dass eine Sprache auf eine andere Sprache <math>L</math> mittels einer <math>f\;</math> reduzierbar ist muss diese Funktion für polynomielle Reduktion zusätzlich in Polynomialzeit berechnet werden können.

Polynomielle Reduktionen werden in der Komplexitätstheorie üblicherweise verwendet um nachzuweisen dass eine der Komplexitätsklasse NP auch NP-vollständig ist.

Als Schreibweise wird hierbei häufig <math>L' L</math> verwendet.

Bücher zum Thema Polynomialzeitreduktion

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

Impressum • Lesezeichen setzen • Seite versenden • Seite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Polynomiale_Reduktion.html">Polynomialzeitreduktion </a>