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-Re...