Questo motiva il concetto di problema difficile per una classe di complessità. Un problema X è difficile per una classe di problemi C se ogni problema in C può essere ridotto a X. Quindi nessun problema in C è più difficile di X, dato che un algoritmo per X ci permette di risolvere qualsiasi problema in C. Naturalmente, la nozione di problemi difficili dipende dal tipo di riduzione utilizzato. Per le classi di complessità superiori a P, vengono comunemente utilizzate riduzioni polinomiali. In particolare, l' insieme dei problemi che sono difficili per NP è l' insieme dei problemi duri per NP.
Che cosa creerebbe un conflitto tra il problema X e il problema C nel contesto della riduzione?
se ogni problema in C può essere ridotto a X