Esistono molte diverse trasformazioni di un problema in un altro, conosciute anche come? Dato il contesto della domanda precedente, scrivi il contesto che contiene la risposta. Può essere da 1 a 20 frasi. Contesto:
Molte classi di complessità sono definite utilizzando il concetto di riduzione. Una riduzione è una trasformazione di un problema in un altro problema. Cattura la nozione informale di un problema che è almeno difficile come un altro problema. Ad esempio, se un problema X può essere risolto usando un algoritmo per Y, X non è più difficile di Y, e diciamo che X si riduce a Y. Ci sono molti diversi tipi di riduzioni, basati sul metodo di riduzione, come le riduzioni di Cook, le riduzioni di Karp e le riduzioni di Levin, e il limite sulla complessità delle riduzioni, come le riduzioni del tempo polinomiale o le riduzioni dello spazio logaritmico.