Un linguaggio A si dice riducibile in tempo polinomiale al linguaggio 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 ∈ A ↔ f ∈ B {\displaystyle w\in A\leftrightarrow f\in B}. Wikipedia