Polynomialzeitreduktion

Polynomialzeitreduktion (Bereich: Zeitkomplexität) 

Man betrachte zwei Probleme A und B. A ist auf B polynomialzeitreduzierbar, falls Problem A durch eine Tranformation in Problem B tranformiert werden kann, und wenn ferner noch die Lösung des Problems B in eine Lösung des Problems A rücktransformiert werden kann und sowohl Transformation als auch Rücktransformation in polynomieller Zeit berechnet (/vorgenommen) werden können.

Es gilt, dass Polynomialzeitreduzierbarkeit transitiv ist.