Ini memotivasi konsep masalah menjadi sulit untuk kelas kompleksitas. Masalah X sulit untuk kelas masalah C jika setiap masalah dalam C dapat dikurangi menjadi X. Dengan demikian tidak ada masalah dalam C lebih sulit daripada X, karena algoritma untuk X memungkinkan kita untuk memecahkan masalah dalam C. Tentu saja, Gagasan masalah sulit tergantung pada jenis pengurangan yang digunakan. Untuk kelas kompleksitas yang lebih besar dari P, pengurangan waktu polinomial biasa digunakan. Secara khusus, set masalah yang sulit untuk NP adalah set masalah NP-keras.
Masalah yang ditetapkan yang sulit untuk ekspresi NP juga bisa dinyatakan bagaimana?
NP-keras
NP-keras
Masalah NNO
yang PRR
ditetapkan VBP
yang PRR
sulit ADJ
untuk PPO
ekspresi NNO
NP NNP
juga ADV
bisa TAME
dinyatakan VBP
bagaimana ADV
? PUN