Cook-Reduktion

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

Polynomiell beschränkte Turingreduktionen werden auch als Cook-Reduktion bezeichnet. Meist bezieht sich der Begriff Polynomialzeitreduktion jedoch auf eine polynomiell beschränkte many-one-Reduktion (auch: Karp-Reduktion).

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.

Schreibweisen

Es existieren unterschiedliche Schreibweisen, darunter

$L \preceq_p L^\prime$

$L \le_{pol} L^\prime$