Polynomzeitreduktion

Eine Sprache $A\subseteq {\mathrm{\Sigma }}^{\ast }$ ist polynomiell reduzierbar auf eine Sprache $B\subseteq {\mathrm{\Sigma }}^{\ast }$ (geschrieben $A{\le }_m^{p}B$), wenn es eine in Polynomzeit berechenbare totale Funktion $f:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Sigma }}^{\ast }$ gibt, sodass für alle $w\in {\mathrm{\Sigma }}^{\ast }$ gilt: