Riduzione in tempo polinomiale

Un linguaggio A si dice riducibile in tempo polinomiale al linguaggio B (denotato con $A{\le }_{P}B$), se esiste una funzione calcolabile f in tempo polinomiale che permetta di convertire istanze del problema di A in istanze di B, tale che $w\in A\leftrightarrow f(w)\in B$.

Questa definizione è molto usata nella teoria della complessità computazionale in quanto se un problema A è riducibile in tempo polinomiale a B allora soluzioni polinomiali di B possono essere usate per risolvere polinomialmente anche A, dato che la composizione di polinomi rimane polinomiale.

Nello specifico con il termine "funzione calcolabile in tempo polinomiale" s'intende una funzione $f:{\mathrm{\Sigma }}^{*}\to {\mathrm{\Sigma }}^{*}$ risolvibile da una macchina di Turing di tempo polinomiale M arrestandosi con soltanto $f(w)$ sul nastro, dopo aver iniziato con qualsiasi w in input.