riduzione in tempo polinomiale

Un linguaggio A si dice riducibile in tempo polinomiale al linguaggio B (denotato con ), se esiste una funzione calcolabile f in tempo polinomiale che permetta di convertire istanze del problema di A in istanze di B, tale che . 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 risolvibile da una macchina di Turing di tempo polinomiale M arrestandosi con soltanto sul nastro, dopo aver iniziato con qualsiasi w in input.