Molte classi di complessità sono definite utilizzando il concetto di riduzione. Una riduzione è una trasformazione di un problema in un altro. Esso coglie la nozione informale di problema almeno altrettanto difficile quanto un altro. Per esempio, se un problema X può essere risolto utilizzando un algoritmo per Y, X non è più difficile di Y e diciamo che X si riduce a Y. Esistono molti tipi diversi di riduzioni, basate sul metodo di riduzione, come le riduzioni Cook, Karp e Levin e la complessità delle riduzioni, come le riduzioni polinomiali o log-space.
La riduzione del tempo polinomio è un esempio di cosa?
la complessità delle riduzioni la complessità delle riduzioni