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.
Apa yang akan menciptakan konflik antara masalah X dan masalah C dalam konteks pengurangan?
jika setiap masalah dalam C dapat dikurangi menjadi X
jika setiap masalah dalam C dapat dikurangi menjadi X
Apa PRI
yang PRR
akan TAME
menciptakan VBT
konflik NNO
antara PPO
masalah NNO
X ADJ
dan CCN
masalah NNO
C ADJ
dalam PPO
konteks NNO
pengurangan NNO
? PUN